XCPC wiki - 树 05 - 树的重链剖分、树上启发式合并

树链剖分 把一棵树分割成若干条链，以便于维护（路径、子树）信息。

重链剖分

重链剖分 (Heavy Path Decomposition) 从树上每个 轻节点 出发，不断向下走 重边，构成一条链。任意点恰好在一条重链中。任意点到根的路径为$\Theta(\log n)$ 条重链和轻边交替形成。

使用两次 DFS 完成重链剖分，时空复杂度$\Theta(n)$。

若$u,v$ 在同一条链上，LCA 是深度较小的那个节点；否则，将链头深度较大的节点跳转到其链头的父节点上，直至两点在同一条链上。复杂度$\Theta(n) - \Theta(\log n)$。

回忆 树的 DFS 序：每个节点在 DFS 中的进出栈的时间序列。每棵子树的 DFS 序都是连续的，且子树上根节点 DFS 序最小；而且，如果优先遍历重子节点，那么同一条链上的节点的 DFS 序也是连续的，且链头节点 DFS 序最小。因此，$u$ 的子树上所有节点的编号介于 dfsn[u] 和 dfsnR[u] 之间，其中 dfsnR[u] 是结束遍历$u$ 的子树的最后一个节点的 DFS 序。

这个良好性质 将树转化为 (广义的) 区间，对$u$ 的 子树 的操作即是对 区间 dfsn[u]$\sim$ dfsnR[u] 的操作。

这支持在$\Theta(\log n)$ 的时间内实现单点修改查询、子树修改查询、路径修改查询，在树根固定的问题中应用广泛。注意，建线段树的时候不是按节点编号建，而是按 DFS 序建。

重链剖分 A（路径信息有交换律，子树区间修改）

重链剖分 B（路径信息不具有交换律，单点修改）

例 树上半群点修改，路径求积：给定$n$ 个结点的树，每个结点$u$ 有一个一次函数$f_u$，有$q$ 个询问：

• $p, a, b$：将$f_p$ 修改为$f_p(x) = ax + b$。
• $u, v, x$：求$f_{pk}(...f_{p1}(f_{p0}(x))) \bmod 998244353$，其中$p_0 = u, p_1, ..., p_k = v$ 是树上简单路径。(Vertex Set Path Composite)

通过树链剖分，将问题转换为$\Theta(\log n)$ 个区间问题。由于复合具有方向性，即不满足交换律，$f_{r}(f_{l}(x)) \neq f_{l}(f_{r}(x))$，因此每条重链需要维护两个不同方向的复合。时间复杂度为预处理$\Theta(n)$，修改$\Theta(\log n)$，查询$\Theta(\log^2 n)$。

template<class info, class mark>
struct SMT {
    int L, R, p, pcnt;
    using pii = struct { info f, b; };
    vector<pii> t;
    vector<mark> m;
    vector<int> ls, rs;

    SMT() {
        init(0, 0);
        t.resize(N << 2);
        m.resize(N << 2);
        ls.resize(N << 2);
        rs.resize(N << 2);
    }

    void init(int l, int r) {
        L = l, R = r;
        p = pcnt = 0;
    }

    void init(int p) {
        t[p] = { info(),info() };
        m[p] = mark();
        ls[p] = rs[p] = 0;
    }

    #define mid ((L+R)>>1)
    #define leaf (R-L<2)
    #define curr p,L,R
    #define lson ls[p],L,mid
    #define rson rs[p],mid,R
    #define self p,int L,int R

    void push_up(int& p) {
        t[p].f = t[ls[p]].f + t[rs[p]].f;
        t[p].b = t[rs[p]].b + t[ls[p]].b;
    }

    void push_down(int& self, const mark& d) {
        if (!p) p = ++pcnt, init(p);
        t[p].f.apply(d, L, R);
        t[p].b.apply(d, L, R);
        m[p].apply(d, L, R);
    }
    void push_down(int& self) {
        if (leaf) return;
        push_down(lson, m[p]);
        push_down(rson, m[p]);
        m[p] = mark();
    }

    // 区间[l,r)修改
    void modify(int& self, int l, int r, const mark& d) {
        if (!p) p = ++pcnt, init(p);
        if (l <= L && R <= r) return push_down(curr, d);
        push_down(curr);
        if (l < mid) modify(lson, l, r, d);
        if (mid < r) modify(rson, l, r, d);
        return push_up(p);
    }
    void modify(int l, int r, const mark& d) {
        if (l >= r) return;
        return modify(curr, l, r, d);
    }

    // 单点修改
    void modify(int& self, int x, const info& d) {
        if (!p) p = ++pcnt, init(p);
        if (leaf) return t[p].apply(d);
        push_down(curr);
        if (x < mid) modify(lson, x, d);
        else modify(rson, x, d);
        return push_up(p);
    }
    void modify(int x, const info& d) {
        return modify(curr, x, d);
    }

    // 查询[l,r)
    pii query(int& self, int l, int r) {
        if (l <= L && R <= r) return t[p];
        push_down(curr);
        if (r <= mid) return query(lson, l, r);
        if (mid <= l) return query(rson, l, r);
        pii les = query(lson, l, r), res = query(rson, l, r);
        return { les.f + res.f, res.b + les.b };
    }
    pii query(int l, int r) {
        if (l >= r) return { info(),info() };
        return query(curr, l, r);
    }
};

struct mark {
    Z a{ inf }, b{ inf };
    void apply(const mark& self)& {
        if (p.a != inf && p.b != inf) {
            a = p.a;
            b = p.b;
        }
    }
};

struct info {
    Z a{ 1 }, b{ 0 };
    void apply(const mark& self)& {
        if (p.a != inf && p.b != inf) {
            a = p.a;
            b = p.b;
        }
    }
    friend info operator + (const info& l, const info& r) {
        return { l.a * r.a, r.a * l.b + r.b };
    }
};

struct TREE {
    int n, unix;
    vector<vector<int>> E;
    vector<int> p, dep, siz, top, dfn, dfnR, seq;
    SMT<info, mark> smt;

    TREE() {}
    TREE(int n) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        E.assign(n, {});
        p.assign(n, -1);
        dep.resize(n);
        siz.resize(n);
        top.resize(n);
        dfn.resize(n);
        dfnR.resize(n);
        seq.resize(n);
        unix = 0;
        smt.init(0, n);  // 线段树初始化
    }

    void add(int u, int v) {
        E[u].push_back(v);
        E[v].push_back(u);
    }

    void work(int s = 0) {
        top[s] = s;
        dep[s] = 0;
        p[s] = -1;
        dfs1(s);
        dfs2(s);
    }

    void dfs1(int u) {
        if (p[u] != -1) E[u].erase(find(E[u].begin(), E[u].end(), p[u]));
        siz[u] = 1;
        for (auto& v : E[u]) {  // 必须加引用
            p[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[E[u][0]]) swap(v, E[u][0]);
        }
    }

    void dfs2(int u) {
        seq[dfn[u] = unix++] = u;
        for (auto& v : E[u]) {
            top[v] = v == E[u][0] ? top[u] : v;
            dfs2(v);
        }
        dfnR[u] = unix;  // 欧拉序：seq[dfnR[u] = unix++] = u;
    }

    // u,v的最近公共祖先
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) u = p[top[u]];
            else v = p[top[v]];
        }
        return dep[u] > dep[v] ? v : u;
    }

    // u到v的路径长度
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    // u是否是v的祖先 v是否在u的子树中
    bool isAncester(int u, int v) {
        return dfn[u] <= dfn[v] && dfn[v] < dfnR[u];
    }

    // u的k级祖先
    int kthAncester(int u, int k) {
        if (dep[u] < k) return -1;
        int d = dep[u] - k;
        while (dep[top[u]] > d) {
            u = p[top[u]];
        }
        return seq[dfn[u] - dep[u] + d];
    }

    // 找u朝向v的第一个儿子
    int getson(int u, int v) {
        if (dep[u] > dep[v]) return -1;
        return kthAncester(v, dep[v] - dep[u] - 1);
    }

    // 修改u-v路径
    void modify_path(int u, int v, const mark& d, bool op) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                smt.modify(dfn[top[u]], dfn[u] + 1, d);
                u = p[top[u]];
            }
            else {
                smt.modify(dfn[top[v]], dfn[v] + 1, d);
                v = p[top[v]];
            }
        }
        if (dep[u] > dep[v]) {
            smt.modify(dfn[v] + op, dfn[u] + 1, d);
        }
        else {
            smt.modify(dfn[u] + op, dfn[v] + 1, d);
        }
    }

    // 查询u-v路径
    info query_path(int u, int v, bool op) {  // op=1 不包含lca
        info les, res;
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                les = les + smt.query(dfn[top[u]], dfn[u] + 1).b;
                u = p[top[u]];
            }
            else {
                res = smt.query(dfn[top[v]], dfn[v] + 1).f + res;
                v = p[top[v]];
            }
        }
        if (dep[u] > dep[v]) {
            les = les + smt.query(dfn[v] + op, dfn[u] + 1).b;
        }
        else {
            res = smt.query(dfn[u] + op, dfn[v] + 1).f + res;
        }
        return les + res;
    }

    // 修改u节点
    void modify_node(int u, const mark& d) {
        smt.modify(dfn[u], dfn[u] + 1, d);
    }
    
    // 查询u节点
    info query_node(int u) {
        return smt.query(dfn[u], dfn[u] + 1).f;
    }
};

int main() {
    int n, q;
    cin >> n >> q;

    TREE tree(n);   // 

    vector<mark> w(n);
    for (int i = 0; i < n; i++) {
        Z a, b;
        cin >> a >> b;
        w[i] = { a, b };
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree.add(u, v);
    }

    tree.work(0);

    for (int i = 0; i < n; i++) {
        tree.modify_node(i, w[i]);
    }

    while (q--) {
        int op;
        cin >> op;
        if (op == 0) {
            int p; Z a, b;
            cin >> p >> a >> b;
            tree.modify_node(p, { a, b });
        } else {
            int u, v; Z x;
            cin >> u >> v >> x;
            auto res = tree.query_path(u, v, 0);
            cout << res.a * x + res.b << endl;
        }
    }

    return 0;
}

求 LCA 的其它方法：

（不用）倍增算法 维护所有结点的深度和$2^k$ 级祖先。先将较深的点跳到相同深度，如果跳到同一个点，直接得到最近公共祖先。否则往上跳相同深度直到成为兄弟结点，其父结点即为最近公共祖先。时间复杂度$\Theta(n \log n) - \Theta(\log n)$，空间复杂度$\Theta(n \log n)$。

（如果要求 O(1) 且 离线 就用这个）并查集 + Tarjan

一个熊孩子给一棵树灌岩浆，他表示很讨厌这种倒着长的树。岩浆会不断的注入，直到注满整个树。显然，岩浆只有在迫不得已的情况下才会向上升高，找到一个新的子树继续注入，并且，根据地转偏向力，岩浆会从左到右地注入。
机(yu)智(chun)的熊孩子发现了找 LCA 的好方法，即如果两个结点都被岩浆烧掉时，他们的 LCA 即为那棵子树上岩浆最高的位置。

遍历完结点$u$ 的子树后, 将$u$ 和其父亲所在集合进行合并。遍历到结点$u$ 时, 对所有询问$u, v$, 若$v$ 已经被遍历过, 则结果为$v$ 所在集合深度最小的结点。复杂度$\Theta(n + q)$。

constexpr int N = 1e5 + 5;
vector<int> E[N];
vector<pair<int, int>> que[N];
int vis[N], ans[N];

struct DSU {} dsu;

void tarjan(int u) {
    vis[u] = 1;  // 访问过 但未回溯 即现在在访问它的子节点
    for (auto v : E[u]) {
        if (vis[v]) continue;
        tarjan(v);
        dsu.uno(u, v);  // 把v合并到u上 方向不能反
    }
    for (auto [v, id] : que[u]) {
        if (vis[v] == 2) ans[id] = dsu.find(v);
    }
    vis[u] = 2;  // 访问过 已回溯 它的子节点已经全部访问过
}

void eachT() {
    int n = read(), Q = read(), st = read();

    dsu.init(n);  // 并查集初始化
    for (int i = 2; i <= n; i++) {
        int u = read(), v = read();
        E[u].push_back(v), E[v].push_back(u);
    }

    for (int i = 1; i <= Q; i++) {
        int u = read(), v = read();
        if (u == v) ans[i] = u;  // 特判
        else que[u].push_back({ v,i }), que[v].push_back({ u,i });
    }  // 存储询问

    tarjan(st);   // dfs
    for (int i = 1; i <= Q; i++) {
        printf("%d\n", ans[i]);
    }
}

（不用）欧拉序 + ST 表 所有进入结点 (包括从子结点回到该结点的事件) 形成长度为$2n - 2$ 的序列，若两个结点没有祖先后代关系，最近公共祖先为左侧的点和右侧的点某个形成区间中深度优先搜索序最小的结点。复杂度为$\Theta(n) - \Theta(1)$。

DSU on Tree 树上启发式合并

树上启发式合并 (DSU on Tree) 用于解决 询问每个节点关于其子树的某些信息 的问题，需离线，且不支持修改。

• 因简单的树形 DP 在空间上不能满足，所以不能存储每个节点的信息，而是要 资源复用。
• 又因为在压缩空间后，需要对每个节点暴力统计子树的信息，在时间上又不能满足，所以 启发式地（基于人类的经验和直观感觉，优化算法）保留重子树的信息，以节约时间。

时间复杂度$\Theta(n\log n)$，空间复杂度$\Theta(n)$。

设某个节点$u$ 的答案需要用到的资源是$\operatorname{info}_u$，

• 遍历所有轻子树，递归求解子树，计算但不保留对$\operatorname{info}_u$ 的影响；
• 遍历重子树，递归求解子树，计算且保留对$\operatorname{info}_u$ 的影响，保留以求解当前节点；
• 遍历所有轻子树，计算对$\operatorname{info}_u$ 的影响，以求解当前节点。

void add(int u) {}  // 增加u对info的影响
void del(int u) {}  // 去除u对info的影响
void cal(int u) {}  // 利用info计算u的ans

void dfs(int u, int p = -1, bool keep = 1) {
    // 遍历轻子树 递归求解
    for (auto& v : E[u]) {
        if (v != p && v != E[u][0]) dfs(v, u, 0);
    }
    
    // 遍历重子树 递归求解 求解当前节点
    if (E[u][0] != p) dfs(E[u][0], u, 1);
    
    // 遍历轻子树 求解当前节点
    add(u);
    for (auto& v : E[u]) {
        if (v != p && v != E[u][0])
            for (int i = dfn[v]; i <= dfnR[v]; i++) add(tdfn[i]);  // 计算对info的影响
    }
    
    // 利用info计算ans
    cal(u);
    
    // 不保留对info的影响 回溯前删除
    if (!keep) {
        for (int i = dfn[u]; i <= dfnR[u]; i++) del(tdfn[i]);  // 删除对info的影响
    }
}

void eachT() {
    dfs1(rt);
    top[rt] = rt, dfs2(rt);
    dfs(rt);
}