C++ – 轻重链剖分

题解 [该代码需要配合线段树]

int cnt;
int fa[maxn];
int dep[maxn];
int siz[maxn];
int son[maxn];
int rk[maxn];
int top[maxn];
int id[maxn];

inline void init_tree() {
    cnt = 0;
}

void dfs_ss(int u) {
    int ms = -1;
    int mss = 0;
    siz[u] = 1;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (fa[u] == v) continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        dfs_ss(v);
        if (mss < siz[v]) {
            mss = siz[v];
            ms = v;
        }
        siz[u] += siz[v];
    }
    son[u] = ms;
}

void dfs_rti(int u, int t) {
    top[u] = t;
    id[u] = ++cnt;
    rk[id[u]] = u;
    if (!~son[u])
        return;
    dfs_rti(son[u], t);
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v != son[u] && v != fa[u])
            dfs_rti(v, v);
    }
}

inline void tree_upd(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        upd(1, 1, n, id[top[x]], id[x], k);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    upd(1, 1, n, id[x], id[y], k);
}

inline long long tree_ask(int x, int y) {
    long long res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res += ask(1, 1, n, id[top[x]], id[x]);
        res %= mod;
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    res += ask(1, 1, n, id[x], id[y]);
    res %= mod;
    return res;
}