洛谷P3384轻重链剖分模板题
树剖模板题。
树剖码量真大(
树剖主要是把树形结构处理成链式结构,从而可以用诸如线段树、树状数组的数据结构进行维护。
学习树剖之前得先会线段树、了解LCA以及树型结构的一些专有名词:树链剖分专有名词图文讲解
1.首先是一个dfs函数,处理出结点的父亲、重儿子、深度、子树重量。非常简单:
1 | void dfs1(long long now, long long fa, long long dep) |
2.然后是另一个dfs函数,用于处理每个结点的dfs序和重链。
1 | void dfs2(long long now, long long tp) |
建线段树的时候,我们是用每个节点的dfs序作为结点编号的(而不是结点原始编号),因为经过两边处理之后,有如下性质:
- 所有子树的dfs序编号都是连续的
- 每条重链上的dfs序编号都是连续的
有了上面两条性质,我们才能用数据结构进行维护。
下面是转自参考资料的一段话
回顾上文的那个题目,修改和查询操作原理是类似的,以查询操作为例,其实就是个LCA,不过这里使用了top来进行加速,因为top可以直接跳转到该重链的起始结点,轻链没有起始结点之说,他们的top就是自己。需要注意的是,每次循环只能跳一次,并且让结点深的那个来跳到top的位置,避免两个一起跳从而擦肩而过。
两个性质:
- 如果$u,v$是一条轻边,那么有$size[u]>=2*size[v]$。这个性质很显然,轻边的话说明$v$是$u$的轻儿子,又因为有$size重>=size轻$,因此有此性质。
- 从根结点到任意结点的路所经过的轻重链的个数必定都小于logn。
不会证明,此性质可以证明树剖的时间复杂度为$O(nlognlogn)$ 。
AC代码:
1 | long long n, m, r, q; |