重链剖分/树链剖分

一、 思想

重链剖分的核心目标是将一棵树的任意路径与任意子树映射为连续的区间（DFN 序），从而将树上路径与子树的修改/查询操作，转化为线性数据结构（通常是线段树或树状数组）的区间操作。

• 子树操作：单个连续区间 $[dfn[u],dfn[u]+sz[u]-1]$，单次操作复杂度 $O(\log n)$。
• 路径操作：任意两点间的树上路径被切分为不超过 $O(\log n)$ 条重链（对应连续的 DFN 区间），单次操作复杂度 $O({\log }^{2}n)$。

---

二、 定义与性质

对于以根节点 $rt$ 为顶点的有根树：

1. 子树大小 $sz[u]$：以 $u$ 为根的子树节点数。
2. 重儿子 $son[u]$：$u$ 的所有子节点中 $sz$ 最大的节点。若有多个取其一；若 $u$ 为叶子节点，则无重儿子。
3. 轻儿子：除重儿子外的其余子节点。
4. 重边 / 轻边：连接父节点与重儿子的边为重边；其余为轻边。
5. 重链：由若干条连续的重边串接而成的极大路径。每个轻儿子作为一条全新重链的链顶（Top）。
6. 链顶 $top[u]$：节点 $u$ 所在重链的深度最小的节点。
7. 原始节点编号$seg[i]$**：$seg[i]=j$,代表dfn序号为i的节点，原始节点编号为j

关键复杂度证明：

若节点 $v$ 是 $u$ 的轻儿子，则必有：

$$sz[v]\le \frac{sz[u]-1}{2}<\frac{sz[u]}{2}$$

推论：从任意节点往根节点跳，每经过一条轻边，子树规模至少翻倍。因此从任意节点到根节点的简单路径上，轻边的数量不超过 $O(\log n)$ 条，即路径最多被分割为 $O(\log n)$ 条重链。

---

三、 两遍 DFS

重链剖分通过两次精简的深搜完成预处理。

1. 第一遍 DFS (dfs1)

• 任务：计算深度 dep、父节点 fa、子树大小 sz，以及确定重儿子 son。
• 逻辑：标准后序遍历，回溯时累加 sz 并贪心挑选最大的子树赋值给 son[u]。

2. 第二遍 DFS (dfs2)

• 任务：分配时间戳 dfn，确定所在链顶 top。
• 核心顺序：必须先递归重儿子，再递归轻儿子。
• 保证同一条重链上的所有节点分配到的 DFN 是严格连续的。
• 某节点 $u$ 的整棵子树节点，其 DFN 必然落在 $[dfn[u],dfn[u]+sz[u]-1]$。

---

四、 树上实现

1. 求最近公共祖先（LCA）与路径遍历

设需要查询/修改 $u$ 与 $v$ 之间的路径：

1. 比较 $top[u]$ 与 $top[v]$ 的深度：将深度更深的链顶所在节点向上跳。
2. 假设 $dep[top[u]]\ge dep[top[v]]$，则当前这一整段重链区间的 DFN 为 $[dfn[top[u]],dfn[u]]$。
3. 对该区间在线段树中执行修改或查询。
4. 更新跳转：$u=fa[top[u]]$。
5. 重复上述步骤，直到 $top[u]==top[v]$（即两点到达同一条重链）。
6. 最后一段区间为深度较浅者到深度较深者：$[min(dfn[u],dfn[v]),max(dfn[u],dfn[v])]$。深度较浅者即为 $\text{LCA}(u,v)$。

2. 子树遍历

以 $u$ 为根的子树，其操作区间严格等价于线性区间：

$$[dfn[u],dfn[u]+sz[u]-1]$$

---

五、 模板

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

vector<int> g[N];
int fa[N], dep[N], sz[N], son[N], top[N], dfn[N], seg[N],timer;

// 第一遍 DFS：确定父节点、深度、子树大小与重儿子
void dfs1(int u, int p, int d) {
    dep[u] = d, fa[u] = p, sz[u] = 1, son[u] = 0;
    for (int v : g[u]) {
        if (v == p) continue;
        dfs1(v, u, d + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

// 第二遍 DFS：重链优先分配连续 DFN 序与链顶
void dfs2(int u, int tp) {
    top[u] = tp, dfn[u] = ++timer,seg[timer]=u;
    if (son[u]) dfs2(son[u], tp);
    for (int v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

// O(log n) LCA 查询
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

// 路径 [u, v] 转化为至多 O(log n) 个连续 DFN 区间
void work_path(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        // 当前连续重链区间: [dfn[top[u]], dfn[u]]
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    // 最终同链区间（点权包含 dfn[u]，边权下压则起始为 dfn[u] + 1）: [dfn[u], dfn[v]]
}

// 子树 u 对应的连续 DFN 区间: [dfn[u], dfn[u] + sz[u] - 1]