重链剖分

重链剖分

定义

重链剖分是树链剖分的一种解决方式，通过树链剖分将树划分为多个连续部分方便执行操作
我们进行如下定义：

• son 表示 u 结点的重儿子。对于重儿子， 我们定义在 u 的所有子树中最大的子节点，且重儿子只有一个
  
• sz 表示 u 结点的子树大小， 包括结点 u 本身
  
• dep 表示 u  结点的深度
  
• dfn 表示 u 结点所表示的 dfs 序
  
• top 表示 u 结点所在链的顶点
  
• fa 表示 u 结点的父节点
  

我们对一棵树进行如下划分，对于每个结点 u ，将其重儿子称为重子结点，而由重儿子所组成的一条链成为重链，其余节点成为轻儿子，特别的，重子节点一定会组成一条链，因为一个节点只存在一个重儿子，所以任何重子结点不存在两个及以上的重子节点。
通过以上分化后，我们可以通过 dfs 对每个结点定义其 dfs 序，对于这个遍历过程，我们采用重儿子优先的策略，优先向重儿子进行递归，可以保证重链的 dfs 序是连续的，并且对于任意一结点 u ，保证其子树内的 dfs 序大于 u  ，并且不超过 dfn + sz - 1
总结就是：

• 重儿子所组成的一定是一条链
  
• 每个节点至多有一个重儿子，满足每个结点均在一条重链上
  
• 重链的 dfs 序是连续的
  
• 子树 u 的 dfs 序范围是 [dfn, dfn + sz - 1]
  

应用

通过以上定义，我们可以通过线段树快速对一个子树内的所有元素进行统一修改，因为一个子树内的所有节点的 dfs 序一定连续
同时，我们还可以快速查询树上最近公共祖先 LCA ，我们可以知道，树上任意一个点 u 都必然存在于一个重链之上，所以两个点只要不断跳到其所在链的顶点，再不断上跳，就能快速找到最近公共祖先；还可以对树上的一条路径进行操作
示例

以洛谷题目 P3384 【模板】重链剖分  为例
初始化

dfs1 ：计算每个子树的大小，以及每个节点的深度，父亲，以及重儿子

1. void dfs1(ll u, ll father) {
2.         fa[u] = father;
3.         dep[u] = dep[father] + 1;
4.         sz[u] = 1;
5.         for (auto v : g[u]) {
6.                 if (v == father) continue;
7.                 dfs1(v, u);
8.                 sz[u] += sz[v];
9.                 if (sz[v] > sz[son[u]]) son[u] = v;
10.         }
11. }

复制代码

dfs2：计算每个节点的 dfs 序，以及每个链的链顶

1. void dfs2(ll u, ll topf) {
2.         top[u] = topf;
3.         dfn[u] = ++timer;
4.         rk[timer] = u;//rk在这里是一个逆数组，用于标记每个dfn所对应的结点，用于后续操作
5.         if (son[u]) dfs2(son[u], topf);
6.         for (auto v : g[u]) {
7.                 if (v != fa[u] && v != son[u])
8.                         dfs2(v, v);
9.         }
10. }

复制代码

线段树模板：

[code]//线段树维护的是dfs序对应的数组 a[rk]，因此树上的子树或路径问题可以转化为数组的区间问题。struct SegmentTree {        void push_up(ll p) {                tree[p] = (tree[p > x >> y;                        cout  x >> y;                        st.add(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, y);                }                if (op == 4) {                        cin >> x;                        cout