树链剖分（HLD）模板

【模板】树链剖分.cpp

// BEGIN 树剖模板
vi g[N];
int fa[N];
int sz[N];
int heavy_son[N];
int dep[N];

void dfs(int u, int f) {
    fa[u] = f;
    sz[u] = 1;
    dep[u] = dep[f] + 1;
    int hson = 0;
    FOR(v, g[u]) {
        if(v!=f) {
            dfs(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[hson]) hson = v;
        }
    }
    heavy_son[u] = hson;
}

int top[N], pos[N];

//https://codeforces.com/blog/entry/22072
void init(int n) { // 很好的写法！
    int idx = 0;
    rng (i, 1, n + 1) {
        if (i != heavy_son[fa[i]]) {
            for (int j = i; j != 0; j = heavy_son[j]) {
                top[j] = i;
                pos[j] = ++idx;
            }
        }
    }
}
// 两种情况：1.修改路径上的边 2.修改路径上的点。
bool VALUE_ON_EDGE = true;
template <class BinOpr>// binary operator
void process_path(int u, int v, BinOpr op) {
    while(top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        op(pos[top[u]], pos[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    op(pos[u] + VALUE_ON_EDGE, pos[v]);
}
// END 树剖模板