树链剖分模板

c++
#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]
树链剖分模板 ​

树链剖分模板
