icontofig | 发布于 2020-04-05 16:24:36 | 阅读量 346 | dsu on tree 树链剖分
发布于 2020-04-05 16:24:36 | dsu on tree 树链剖分
CodeForces 600E.Lomsat gelral dsu on tree 树上启发式合并
Example15 1 2 3 1 2 3 3 1 1 3 2 2 1 2 3 1 2 1 3 1 4 1 14 1 15 2 5 2 6 2 7 3 8 3 9 3 10 4 11 4 12 4 136 5 4 3 2 3 3 1 1 3 2 2 1 2 3题目大意给出一棵有根树,树上每个点有一个颜色,求问以每一个节点x为根的子树内数量最多的颜色的编号的和sum为多少。 题解如果暴力统计的话,时间复杂度将会成为O(n2),这是我们没办法接受的。 貌似可以搞什么线段树合并还有莫队什么的。 但是复杂度好像依旧还是太高,于是就有这么一个神奇的东西叫dsu on tree,中文名叫树上启发式合并。
继续阅读