首页 > 笔记 > 树剖进阶总结

树剖进阶总结

再来一篇

树链剖分

我们先搞棵树

如果只要子树操作?可以发现子树是DFS序上一段连续区间。。

而且区间的大小就是子树的大小(很明显啊

那么怎么处理路径问题?

我们可以发现dfs序是一些小的路径拼起来的

实际上,每个点第一个被访问的子树就会和它形成一条路径,我们就把这棵树剖成了很多条路径,询问的一条路径就可以分成这些小路径。

我们就是要找一种比较好的方法,让每条询问的路径都分成尽量少的短。

怎么?随机?感觉非常不靠谱。

那就按子树大小加权随机?用不到。直接剖较大的就可以了

一个点的子树最大的儿子叫重儿子,这条边叫做重边。一条由重边组成的链叫做重链。

显然一条路径只会有$O(\log n)$条重边。

然后我们dfs一次求出重儿子,再dfs一遍求出dfs序。这样每个重链在dfs序上就是连续的区间。用数据结构维护下dfs序就可以了。

一般的题用线段树就可以维护了。

例题

luogu3384

就是模版啊。。

luogu3250

查询的是不包含x的链的权值最大值。
树链剖分后,每条链变成O(logn)个区间,那么未被这个链包含的也有logn个区间,在这logn个区间上做修改即可。
因为有删除操作,每个线段树节点开一个堆维护。

luogu3313

这题是非常有趣的一道题。我们对于每一种宗教开一棵线段树。但是不能开全,就是动态开点的线段树。每次要改的时候就加入新点。(有种主席树即视感


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×