dsu on the tree 详解

前置知识

最好要会简单的树链剖分,~~然而我并不会~~。

dsu on the tree 是什么?

树上启发式合并

你可能觉得非常的高端,但是继续往下看你就会觉得~~非常的亲和了~~

首先我们先看一个加快算法复杂度的简单例子

给定你一个数列,然后告诉你[l,r]区间的值,让你求[l,r+1]的值。

非常naive的做法,把 [l,r+1] for一遍 复杂度o(n)

其实我们可以利用 [l,r] ,然后加上[a_r+1]的值 复杂度o(1)

我们可以把这种思想利用在树上,对于每一个节点,可以利用他的size最大节点,也就是他的重儿子,这样就可以降低复杂度

然后我们暴力对轻儿子来进行操作

伪代码的解释

先递归计算轻儿子子树,递归结束时删除子树的贡献
再递归计算重儿子子树,保留它的贡献
再计算当前子树中所有轻子树的贡献
如果当前子树是父节点的轻子树,消除当前子树的贡献

伪代码

如果没有学过树链剖分的话,下面给出一份找重儿子的代码

我们来分析一下时间复杂度

显然只有轻边才会进行合并

而一个节点到根节点的路径中,有logn条轻边和logn条重链

一个点的信息只会合并logn

于是复杂度就是onlogn*一个点修改的复杂度 是不是非常的优越?

我们在来想想dfs序和莫队的联系,是不是感觉非常的相似?

附加一点 : dsu on the tree做法必须需要离线,并且信息要具有可合并的性质

接下来就是题目推荐了

模板题

http://codeforces.com/contest/600/problem/E

比较简单的应用

http://codeforces.com/problemset/problem/246/E

比较难的应用

http://codeforces.com/problemset/problem/741/D

参考资料

http://www.cnblogs.com/candy99/p/dsuontree.html

http://codeforces.com/blog/entry/44351#comment-332425

http://blog.csdn.net/Clove_unique/article/category/6772173

update:什么你说我推荐的题代码都不放??

对我就是不放,给你伪代码你自己去写~~233~~

发表评论

电子邮件地址不会被公开。 必填项已用*标注