重链剖分
重链剖分定义
重链剖分是树链剖分的一种解决方式，通过树链剖分将树划分为多个连续部分方便执行操作
我们进行如下定义：
[*]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 + sz - 1]
应用
通过以上定义，我们可以通过线段树快速对一个子树内的所有元素进行统一修改，因为一个子树内的所有节点的 dfs 序一定连续
同时，我们还可以快速查询树上最近公共祖先 LCA ，我们可以知道，树上任意一个点 u 都必然存在于一个重链之上，所以两个点只要不断跳到其所在链的顶点，再不断上跳，就能快速找到最近公共祖先；还可以对树上的一条路径进行操作
示例
以洛谷题目 P3384 【模板】重链剖分为例
初始化
dfs1 ：计算每个子树的大小，以及每个节点的深度，父亲，以及重儿子
void dfs1(ll u, ll father) {
fa = father;
dep = dep + 1;
sz = 1;
for (auto v : g) {
if (v == father) continue;
dfs1(v, u);
sz += sz;
if (sz > sz]) son = v;
}
}dfs2：计算每个节点的 dfs 序，以及每个链的链顶
void dfs2(ll u, ll topf) {
top = topf;
dfn = ++timer;
rk = u;//rk在这里是一个逆数组，用于标记每个dfn所对应的结点，用于后续操作
if (son) dfs2(son, topf);
for (auto v : g) {
if (v != fa && v != son)
dfs2(v, v);
}
}线段树模板：
//线段树维护的是dfs序对应的数组 a]，因此树上的子树或路径问题可以转化为数组的区间问题。struct SegmentTree { void push_up(ll p) { tree = (tree, dfn + sz - 1, y); } if (op == 4) { cin >> x; cout
页:
[1]