首页 > 小 Q 与树

lifehappy

发表于 2021-04-27 20:14:22

小 Q 与树给定一棵带权的树，每条边的距离都为，要我们求，如果考虑 dsu on tree，则是枚举，分两种情况统计答案：，则，则我们只要知道集合中有多少个点，以及即可，设点的个数为，，则上式等价于。，则，则我们只要知道，以及即可求得答案，上式等价于。所以可以对点权离展开全文

CYCAlex

发表于 2021-04-27 10:38:09

给出一颗树，结点权值为求：思路本题为点分治模板题以重心为根，用 solve(x) 解决子树内贡献每次 solve(x) 时，首先得到经过该点和不经过该点的贡献总和 calc(x, fa, 0) 这个过程首先利用 dfs_dis(x, fa, 0) 得到以为根的链信息展开全文

GsjzTle

发表于 2021-07-01 15:34:07

题目大意给定一棵包含个节点的树，每个节点有个权值求解题思路对于节点记权值小于的节点有记权值大于等于的节点有那么节点对答案的贡献为：即：定义为当前子树的根，那么开四棵权值树状数组，分别用来维护、、、然后跑一遍即可展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛