树链剖分（重链剖分）入门到实践：原理、模板与例题

树链剖分是竞赛中处理树上路径问题的利器，本文带你从零开始掌握它。

一、什么是树链剖分？
将树划分成若干条重链，使得任意两点间的路径可以拆分为 O(log n) 条重链的连续段。然后在线段树上对这些段进行操作。

二、核心概念

• 重儿子：子树最大的儿子节点


• 轻儿子：其余儿子


• 重边：父节点连向重儿子的边


• 轻边：其余边


• 重链：连续重边构成的链

• 计算子树大小 sz


• 确定重儿子 son


• 计算深度 dep 和父节点 fa

• 分配 DFS 序 dfn


• 确定链顶 top


• 重儿子优先访问（保证重链 DFS 序连续）

void path_update(int x, int y, int val) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update(1, 1, n, dfn[top[x]], dfn[x], val);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    update(1, 1, n, dfn[x], dfn[y], val);
}

• 树上路径最值/和/异或


• 子树修改/查询（子树 DFS 序连续）


• LCA（dep[top] 比较法）


• P4178 Tree（点分治 + 树剖 LCA）

• 预处理：O(n)


• 路径操作：O(log² n)


• 常数小，实际表现优秀

• 洛谷 P3384 轻重链剖分（模板）


• 洛谷 P3178 树上操作


• 洛谷 P4315 月下"毛景树"（边权版本）