icontofig | 发布于 2020-04-16 22:28:40 | 阅读量 467 | 树链剖分
发布于 2020-04-16 22:28:40 | 树链剖分
2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet
题目大意给出一棵n个节点的树,要求将这个树的所有节点映射到一张1000000*20的横向表格里,要求保持原先的连边映射成的相连线段不能有交叉。 输出一种方案,要求将所有的树上节点的坐标输出。 题解行数最多只有20行,所以要考虑最大行数控制在log2n以内。所以就要想树上的什么东西一定小于小于等于log2n。 学过树链剖分的话不难想到,对一个树进行重链剖分的话,所有点向下的轻链长度一定小于等于log2n,树链剖分的复杂度就是基于这个性质证明的。这个性质的证明并不难想,因为对于一个节点x,其轻儿子的子树大小一定不会超过siz[x]/2,否则这个儿子就是重儿子了。 然后就可以明白,要先对树进行重链剖
继续阅读
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,中文名叫树上启发式合并。
继续阅读