首页 > Colorful Tree
开通博客写题解
头像 rk_no
发表于 2020-11-07 17:17:35
题目： 给一棵无根树。每个点有一个颜色。个操作。：将结点的颜色修改为；：问所有颜色为的结点的生成树大小。(若不存在颜色为的结点输出) 做法： 这题好神奇。可以用序来维护相同颜色结点的生成树。考虑若颜色的只有个结点、，则其生成树大小就是两个结点在原树上的距离，记为。此时，如果加入第个结点，对生成树的 展开全文
去ta的博客 赞 (7) 回复(3) 收起
头像 lifehappy
发表于 2020-11-11 21:29:11
Colorful Tree rk_no巨巨TQL /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int head[N], to[N & 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-11-07 22:32:44
好难写....完全想不到,也不会证明 抄的https://ac.nowcoder.com/acm/problem/blogs/200179 好厉害呜呜 #include <bits/stdc++.h> using namespace std; typedef long long ll; 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 Kur1su
发表于 2020-11-11 17:38:10
Description 给出一棵树，每个节点都有颜色。对树有两种操作:U x c 更新操作，将x节点的颜色变成cQ c 查询所有颜色为c的节点形成的子图有多少条边 Solution 完全没思路。。。看了其他聚聚的题解通过找规律可以看出加入每条边x的贡献是 因此可以用一个set来维护每个颜色的序列，然 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 林思艺
发表于 2020-11-10 16:11:44
题意 你有一颗树，每个点有一个颜色，有次操作， 将 节点改为颜色 。询问所有颜色为 的点的生成树大小。 分析 我们可以用序来维护每种颜色的生成树大小。考虑若颜色为的节点只有个、，则其生成树大小就是两个结点在树上的距离，记为。此时，如果加入第个结点，对生成树的贡献能用树上距离算出来： 我们分类讨论： 展开全文
去ta的博客 赞 (3) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”