学习笔记：重链剖分

CGcgxyXY · 2026-09-25 21:47:14 · 算法·理论

引入

P3384 【模板】重链剖分 / 树链剖分

给定一棵有根树，需要支持以下操作：

• 路径加
• 子树加
• 路径和
• 子树和

如果只有子树加子树和，直接转到 dfs 序上就是区间加区间和，容易维护。

但是还有路径操作，如果用线段树维护，暴力做一次操作复杂度 O(n\log n)，不可接受。

由于路径单独拿出来是一条链，考虑把树划分为若干条链，在每一条链上面修改。
可以将这若干条链放到一个序列上，让一条链上面的节点在连续的位置，然后使用维护序列的数据结构维护。

由于需要支持子树操作，需要让这个序列仍然是一个合法的 dfs 序，以支持子树操作。
那么每一条链都需要是后代到若干个祖先的形态。

例如下图就是一棵树的划分方式。

图中 1-3-6-9，4-8 组成两条链，2,5,7 单点分别看作一条链。

那么组成的一个合法序列对应节点就是 1,3,6,9,5,7,2,4,8。

这样链的操作就变成了若干个序列操作。

注意到这样转化后的操作的复杂度和路径被划分成的链的数量直接相关，所以需要找到一个合适的方式，使得一条路径被划分成的链的数量尽可能少。

首先如果一个非叶节点下面没有接其他的链，那么接上一条链肯定是不劣的，因为这样减少了子树内到根上的链的数量。

重链剖分

记 sz_u 为点 u 的子树大小（即子树内节点数量）。
记点 u 的重儿子是 u 子树大小最大的儿子，记为 son_u。

那么把 u-son_u-son_{son_u}-\dots 划分成一条链，直到到达叶子节点，这样的链记为一条重链，u 为这条链的链顶。
或者说，对于每个节点，它和它的重儿子连成重边，重边组成的极大链就是重链；链顶是重链中深度最小的节点。

记 (u,son_u) 是一条重边，(u,v)(v \ne son_u) 为一条轻边。

那么可以证明，任意一个节点到根的路径上最多有 O(\log_2 n) 条重链。

一个节点到根的路径上重链的数量显然为经过的轻边数量加一。

记 u 是一个链顶，那么 (fa_u,u) 是一条轻边。
所以 sz_u \leq sz_{son_{fa_u}}，sz_{fa_u} \geq sz_u +sz_{son_{fa_u}}+1 > 2sz_u。
这样就有每个轻子树的大小都不超过父节点的一半。
换句话说，从 u 一直向父亲跳，每经过一条轻边，子树大小至少翻倍。

由于总结点数为 n，那么一个节点到根路径上的轻边数量最多会有 O(\log_2 n) 条。

这样，路径 u,v 上的重链数量 \leq O(\log n)+O(\log n)=O(\log n)。

所以一条路径就被重链剖分转化成了 O(\log n) 条重链，或者 dfs 序上的 O(\log n) 个区间。

以下给出代码实现。 :::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 1e5 + 5;
int n, m, rt, mod;
int a[N];
vector<int> g[N];
int fa[N], sz[N], dep[N], son[N];
void dfs1(int u, int pr){
    fa[u] = pr;
    sz[u] = 1;
    dep[u] = dep[pr] + 1;
    for (int v : g[u]) if (v != pr){
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}
int top[N], dfn[N], nod[N], cnt;
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++cnt;
    nod[cnt] = u;
    if (!son[u]) return;
    dfs2(son[u], tp);
    for (int v : g[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> rt >> mod;
    rep(u, 1, n) cin >> a[u];
    rep(i, 2, n){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(rt, 0);
    dfs2(rt, rt);
    return 0;
}

::: 其中 fa[u] 为 u 的父节点，dep[u] 为 u 的深度（到根路径上的节点数量），son[u] 为 u 的重儿子编号，top[u] 为 u 所在重链的链顶，dfn[u] 为 u 在序列上的位置，nod[x] 为序列第 x 个位置上对应的节点编号。

根据上面的过程，可以发现重链剖分这个 O(\log n) 的上界是很严格的，并且只有特殊的数据才能卡满，例如完全二叉树。
:::info[一种常见的数据构造方式，能把树剖的复杂度卡的比较满，同时卡掉暴力] 建立一棵 \sqrt n 个结点的二叉树。
对于每个结点到其儿子的边，我们将其替换成一条长度为 \sqrt n 长度的链。

这样可以将随机询问轻重链切换次数卡到平均 \frac{\log_2 n}{2} 次，同时有 O(\sqrt n \log n) 的深度。

于是需要区间加区间求和操作，这里使用线段树直接维护即可（代码中使用了标记永久化）。

这里讲一下路径操作的细节：

对于给定的两个节点 u,v，不断选择链顶深度更大的节点，统计 / 修改信息并向上跳到上一个重链，直到两个节点在同一条链上。
此时需要额外统计两个节点之间链的信息。

如图，top_u 深度更大，统计 [dfn_{top_u},dfn_u] 的信息，然后令 u \leftarrow fa_{top_u}。

P3384 完整实现： :::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 1e5 + 5;
int n, m, rt, mod;
int a[N];
vector<int> g[N];
int fa[N], sz[N], dep[N], son[N];
void dfs1(int u, int pr){
    fa[u] = pr;
    sz[u] = 1;
    dep[u] = dep[pr] + 1;
    for (int v : g[u]) if (v != pr){
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}
int top[N], dfn[N], nod[N], cnt;
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++cnt;
    nod[cnt] = u;
    if (!son[u]) return;
    dfs2(son[u], tp);
    for (int v : g[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}
struct node {
    int len, sum, tag;
    void add(int x){
        sum = (sum + 1ll * len * x) % mod;
        tag = (tag + x) % mod;
    }
} t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((pl+pr)>>1)
void up(int p){
    t[p].sum = (t[ls].sum + t[rs].sum + 1LL * t[p].tag * t[p].len) % mod;
}
void build(int p, int pl, int pr){
    t[p].len = pr - pl + 1;
    if (pl == pr){
        t[p].sum = a[nod[pl]];
        return;
    }
    build(ls, pl, mid);
    build(rs, mid + 1, pr);
    up(p);
}
void add(int p, int pl, int pr, int l, int r, int x){
    if (l <= pl && pr <= r) return t[p].add(x);
    if (l <= mid) add(ls, pl, mid, l, r, x);
    if (r > mid) add(rs, mid + 1, pr, l, r, x);
    up(p);
}
int sum(int p, int pl, int pr, int l, int r, int tag){
    if (l <= pl && pr <= r) return(t[p].sum + 1LL * t[p].len * tag) % mod;
    tag = (tag + t[p].tag) % mod;
    int res = 0;
    if (l <= mid) res += sum(ls, pl, mid, l, r, tag);
    if (r > mid) res += sum(rs, mid + 1, pr, l, r, tag);
    return res % mod;
}
void add_subtree(int u, int x){
    add(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, x);
}
void add_path(int u, int v, int x){
    while (top[u] != top[v]){
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        add(1, 1, n, dfn[top[u]], dfn[u], x);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    add(1, 1, n, dfn[u], dfn[v], x);
}
int sum_subtree(int u){
    return sum(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, 0);
}
int sum_path(int u, int v){
    int res = 0;
    while (top[u] != top[v]){
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res = (res + sum(1, 1, n, dfn[top[u]], dfn[u], 0)) % mod;
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res = (res + sum(1, 1, n, dfn[u], dfn[v], 0)) % mod;
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> rt >> mod;
    rep(u, 1, n) cin >> a[u];
    rep(i, 2, n){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(rt, 0);
    dfs2(rt, rt);
    build(1, 1, n);
    while (m--){
        int op, u, v, x;
        cin >> op;
        if (op == 1){
            cin >> u >> v >> x;
            add_path(u, v, x);
        }
        else if (op == 2){
            cin >> u >> v;
            cout << sum_path(u, v) <<  '\n';
        }
        else if (op == 3){
            cin >> u >> x;
            add_subtree(u, x);
        }
        else if (op == 4){
            cin >> u;
            cout << sum_subtree(u) <<  '\n';
        }
    }
    return 0;
}

:::

分析一下复杂度：

这里使用线段树维护区间加区间求和，算上重链剖分的辅助数组，空间复杂度是 O(n) 的。

预处理的 dfs 部分复杂度是线性的，为 O(n)。

线段树建树同样是 O(n)。

对于一次子树操作，只需要对子树对应的 dfs 序做区间修改 / 查询，只需要在线段树对应的 [dfn_u,dfn_u+sz_u-1] 区间上操作即可，复杂度是线段树的 O(\log n)。

对于一次路径操作，路径被分为了 O(\log n) 条重链，每条重链进行一次区间操作，复杂度是 O(\log^2n) 的。

总复杂度可以看作 O(n + m\log^2 n)。

重链剖分求解最近公共祖先

容易发现，在上述查询过程中，u,v 跳到同一条重链上之后，深度较小的节点就是 \operatorname{lca}(u,v)。

复杂度为跳过的重链数量，为 O(\log n)。

如果只需要求 \operatorname{lca}(u,v)，代码可以精简一些，可以参考下面给出的 P3379 【模板】最近公共祖先（LCA） 实现。

时间复杂度 O(n+m \log n)，空间复杂度 O(n)。 :::info[Code]

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, rt;
vector<int> g[N];
int fa[N], dep[N], sz[N], son[N];
void dfs1(int u, int pr){
    fa[u] = pr;
    dep[u] = dep[pr] + 1;
    sz[u] = 1;
    for (int v : g[u]) if (v != pr){
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}
int top[N];
void dfs2(int u, int tp){
    top[u] = tp;
    for (int v : g[u]) if (v != fa[u]) dfs2(v, v == son[u] ? tp : v);
}
int lca(int u, int v){
    while (top[u] != top[v]) dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
    return dep[u] < dep[v] ? u : v;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> rt;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(rt, 0);
    dfs2(rt, rt);
    while (m--){
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) <<  '\n';
    }
    return 0;
}

:::

例题

P2590 [ZJOI2008] 树的统计

Description

给出一棵树，每个点有点权。
需要支持三种操作：

• 单点修改
• 路径最大值
• 路径和

  Solution

  树剖之后直接上线段树维护就做完了。

直接做是简单的，但是这里介绍一种减小常数的技巧：

当只有路径操作时，数据结构可以单独维护每一条链，而不是所有节点。
例如线段树，可以动态开点，每一条重链开一棵线段树，只需要预处理的时候额外记录链底即可。

Code

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 3e4 + 5;
int n, m;
int a[N];
vector<int> g[N];
int fa[N], sz[N], dep[N], son[N];
void dfs1(int u, int pr){
    fa[u] = pr;
    sz[u] = 1;
    dep[u] = dep[pr] + 1;
    for (int v : g[u]) if (v != pr){
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}
struct node {
    int lson, rson;
    int sum, mx;
} t[N<<2];
int rt[N], ct;
int top[N], bot[N], dfn[N], nod[N], cnt;
#define ls t[p].lson
#define rs t[p].rson
#define mid ((pl+pr)>>1)
void up(int p){
    t[p].sum = t[ls].sum + t[rs].sum;
    t[p].mx = max(t[ls].mx, t[rs].mx);
}
void build(int & p, int pl, int pr){
    p = ++ct;
    if (pl == pr){
        t[p].sum = t[p].mx = a[nod[pl]];
        return;
    }
    build(ls, pl, mid);
    build(rs, mid + 1, pr);
    up(p);
}
void upd(int p, int pl, int pr, int x, int v){
    if (pl == pr){
        t[p].sum = t[p].mx = v;
        return;
    }
    x <= mid ? upd(ls, pl, mid, x, v) : upd(rs, mid + 1, pr, x, v);
    up(p);
}
int sum(int p, int pl, int pr, int l, int r){
    if (l <= pl && pr <= r) return t[p].sum;
    int res = 0;
    if (l <= mid) res += sum(ls, pl, mid, l, r);
    if (r > mid) res += sum(rs, mid + 1, pr, l, r);
    return res;
}
int mx(int p, int pl, int pr, int l, int r){
    if (l <= pl && pr <= r) return t[p].mx;
    int res =-1e9;
    if (l <= mid) res = max(res, mx(ls, pl, mid, l, r));
    if (r > mid) res = max(res, mx(rs, mid + 1, pr, l, r));
    return res;
}
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++cnt;
    bot[u] = u;
    nod[cnt] = u;
    if (!son[u]) return build(rt[tp], dfn[tp], dfn[u]);
    dfs2(son[u], tp);
    bot[u] = bot[son[u]];
    for (int v : g[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}
void change(int u, int x){
    upd(rt[top[u]], dfn[top[u]], dfn[bot[u]], dfn[u], x);
}
int qmax(int u, int v){
    int res =-1e9;
    while (top[u] != top[v]){
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res = max(res, mx(rt[top[u]], dfn[top[u]], dfn[bot[u]], dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res = max(res, mx(rt[top[u]], dfn[top[u]], dfn[bot[u]], dfn[u], dfn[v]));
    return res;
}
int qsum(int u, int v){
    int res = 0;
    while (top[u] != top[v]){
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += sum(rt[top[u]], dfn[top[u]], dfn[bot[u]], dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res += sum(rt[top[u]], dfn[top[u]], dfn[bot[u]], dfn[u], dfn[v]);
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    rep(i, 2, n){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    rep(u, 1, n) cin >> a[u];
    dfs1(1, 0);
    dfs2(1, 1);
    cin >> m;
    while (m--){
        string op;
        int x, y;
        cin >> op >> x >> y;
        if (op ==  "CHANGE") change(x, y);
        else if (op ==  "QMAX") cout << qmax(x, y) <<  '\n';
        else if (op ==  "QSUM") cout << qsum(x, y) <<  '\n';
    }
    return 0;
}

:::

P4114 Qtree1

Description

给出一棵树，每条边有边权。
需要支持两种操作：

• 修改一条边的边权
• 查询路径上边权最大值

Solution

介绍一个技巧：边转点。

由于每个节点的父节点唯一，所以可以把一条边的边权转成深度较大的一个端点的点权，这样就可以直接做了。
特别地，根节点的权值没有定义。

需要注意的是，边转点之后路径操作不能涉及到 \operatorname{lca}(u,v) 的点权。

Code

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 1e5 + 5;
int n, m;
int eu[N], ev[N];
vector<pair<int, int>> g[N];
int fa[N], sz[N], dep[N], son[N], wt[N];
void dfs1(int u, int pr){
    fa[u] = pr;
    sz[u] = 1;
    dep[u] = dep[pr] + 1;
    for (auto[v, w] : g[u]) if (v != pr){
        wt[v] = w;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}
struct node {
    int lson, rson;
    int mx;
} t[N<<2];
int rt[N], ct;
int top[N], bot[N], dfn[N], nod[N], cnt;
#define ls t[p].lson
#define rs t[p].rson
#define mid ((pl+pr)>>1)
void up(int p){
    t[p].mx = max(t[ls].mx, t[rs].mx);
}
void build(int & p, int pl, int pr){
    p = ++ct;
    if (pl == pr){
        t[p].mx = wt[nod[pl]];
        return;
    }
    build(ls, pl, mid);
    build(rs, mid + 1, pr);
    up(p);
}
void upd(int p, int pl, int pr, int x, int v){
    if (pl == pr){
        t[p].mx = v;
        return;
    }
    x <= mid ? upd(ls, pl, mid, x, v) : upd(rs, mid + 1, pr, x, v);
    up(p);
}
int mx(int p, int pl, int pr, int l, int r){
    if (l <= pl && pr <= r) return t[p].mx;
    int res =-1e9;
    if (l <= mid) res = max(res, mx(ls, pl, mid, l, r));
    if (r > mid) res = max(res, mx(rs, mid + 1, pr, l, r));
    return res;
}
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++cnt;
    bot[u] = u;
    nod[cnt] = u;
    if (!son[u]) return build(rt[tp], dfn[tp], dfn[u]);
    dfs2(son[u], tp);
    bot[u] = bot[son[u]];
    for (auto [v, w] : g[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}
void change(int i, int x){
    int u = dep[eu[i]] > dep[ev[i]] ? eu[i] : ev[i];
    upd(rt[top[u]], dfn[top[u]], dfn[bot[u]], dfn[u], x);
}
int qmax(int u, int v){
    int res = 0;
    while (top[u] != top[v]){
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res = max(res, mx(rt[top[u]], dfn[top[u]], dfn[bot[u]], dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    if (u != v) res = max(res, mx(rt[top[u]], dfn[top[u]], dfn[bot[u]], dfn[u] + 1, dfn[v]));
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    rep(i, 1, n - 1){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        eu[i] = u, ev[i] = v;
    }
    dfs1(1, 0);
    dfs2(1, 1);
    string op;
    while (cin >> op){
        if (op ==  "DONE") break;
        int x, y;
        cin >> x >> y;
        if (op ==  "CHANGE") change(x, y);
        else if (op ==  "QUERY") cout << qmax(x, y) <<  '\n';
    }
    return 0;
}

:::

P4116 Qtree3

Description

给出一棵 n 个点的树，节点有黑白两种颜色，初始全为白。

有两种操作：

• 反转一个点的颜色

• 询问 1 到 u 的路径上的第一个黑点的编号。

Solution

看作维护一个点集，每次查询 1 到 u 路径上最浅的节点的编号。

考虑分成若干条重链，查询每条重链上最浅的节点的编号。

可以直接维护一个以 dfn_u 为键值的 set，每次直接在链上使用 s.lower_bound(dfn[top[u]]) 查询即可。

但是发现如果每条重链开一个 set，每次只需要取出 s[top[u]].begin()，判断其是否在 [dfn_{top_u},dfn_u] 内即可，单次询问复杂度 O(\log n)。

时间复杂度 O(n+m\log n)，空间复杂度 O(n)。

Code

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 1e5 + 5;
int n, q;
int a[N];
vector<int> g[N];
int fa[N], sz[N], dep[N], son[N];
void dfs1(int u, int pr){
    fa[u] = pr;
    sz[u] = 1;
    dep[u] = dep[pr] + 1;
    for (int v : g[u]) if (v != pr){
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}
int top[N];
void dfs2(int u, int tp){
    top[u] = tp;
    for (int v : g[u]) if (v != fa[u]) dfs2(v, v == son[u] ? tp : v);
}
set<pair<int, int>> s[N];
void upd(int u){
    if (a[u]) s[top[u]].erase({dep[u], u});
    else s[top[u]].insert({dep[u], u});
    a[u] ^= 1;
}
int query(int u){
    int res =-1;
    while (u){
        if (!s[top[u]].empty() && (*s[top[u]].begin()).first <= dep[u]) res = (*s[top[u]].begin()).second;
        u = fa[top[u]];
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    rep(i, 2, n){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    while (q--){
        int op, u;
        cin >> op >> u;
        if (!op) upd(u);
        else cout << query(u) <<  '\n';
    }
    return 0;
}

:::

P3979 遥远的国度

Description

给定一棵树，有点权，支持以下操作：

• 换根
• 路径赋值
• 子树最小值

Solution

路径赋值是简单的，考虑如何维护换根操作。

重点在于如何求出以 rt 为根时，点 u 子树对应的节点是哪些。

如图，考虑 rt 的位置不同时，u 的子树对应哪些节点。
（下文中祖先关系都是在以 1 为根的情况下讨论。）

如果 rt \not \in subtree_u，那么 rt 为根时 u 的子树还是 subtree_u，对应 dfs 序为 [dfn_u,dfn_u+sz_u)。
如果 rt=u，那么 u 的子树就是整棵树，对应 dfs 序为 [1,n]。
否则，记 rt 祖先中 u 的儿子节点为 v，那么 rt 为根时 u 的子树为 T \setminus subtree_v，即扣掉 v 子树之后的所有点，对应 dfs 序为 [1,dfn_v) \cup [dfn_v+sz_v,n]。

发现这样仍然可以用一棵全局的线段树维护，于是只需要考虑 rt 在 u 子树内时如何找到 v。

这里提供三种方法。
第一种是长剖找 rt 的第 dep_{rt}-dep_u+1 级祖先，但是我不会，所以不做介绍。
第二种是利用树剖重链 dfs 序连续的特性直接向上跳，到了同一条链上可以 O(1) 访问 k 级祖先，复杂度 O(\log n)。
第三种是把存边的 vector 只保留每个点连向儿子的边，然后把重儿子放到第一个再继续 dfs，访问时每个儿子的 dfn_v 自然是递增的，可以直接二分查找最后一个 dfn_v \leq dfn_{rt} 的儿子，复杂度同样 O(\log n)。

预处理复杂度 O(n)，修改复杂度 O(\log ^2n)，查询复杂度 O(\log n)。
空间线性。

Code

第二种扩展性强一点，这里给出二三两种方式实现的代码。
:::info[Code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 1e5 + 5, INF = 0x7fffffff;
int n, m, rt;
int a[N];
vector<int> g[N];
int fa[N], dep[N], sz[N], son[N];
void dfs1(int u, int pr){
    fa[u] = pr;
    sz[u] = 1;
    dep[u] = dep[pr] + 1;
    if (pr) g[u].erase(find(g[u].begin(), g[u].end(), pr));  //sol 2
    for (int v : g[u]){
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}
int top[N], dfn[N], nod[N], cnt;
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++cnt;
    nod[cnt] = u;
    rep(i, 0, (int)g[u].size() - 1) if (g[u][i] == son[u]) swap(g[u][0], g[u][i]);  //sol 2
    if (!son[u]) return;
    dfs2(son[u], tp);
    for (int v : g[u]) if (v != son[u]) dfs2(v, v);
}
int find1(int x, int u){//sol 1
    int dept = dep[u] + 1;
    while (dep[top[x]] > dept) x = fa[top[x]];
    return nod[dfn[x] - dep[x] + dept];
}
int find2(int x, int u){//sol 2
    return g[u][upper_bound(g[u].begin(), g[u].end(), x, [](int x, int y){return dfn[x] < dfn[y];}) - g[u].begin() - 1];
}
struct node {
    int mn, tag;
    void cov(int x){
        mn = tag = x;
    }
} t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((pl+pr)>>1)
void up(int p){
    t[p].mn = min(t[ls].mn, t[rs].mn);
}
void down(int p){
    if (t[p].tag !=-1){
        t[ls].cov(t[p].tag);
        t[rs].cov(t[p].tag);
        t[p].tag =-1;
    }
}
void build(int p, int pl, int pr){
    t[p].tag =-1;
    if (pl == pr){
        t[p].mn = a[nod[pl]];
        return;
    }
    build(ls, pl, mid);
    build(rs, mid + 1, pr);
    up(p);
}
void upd(int p, int pl, int pr, int l, int r, int x){
    if (l <= pl && pr <= r) return t[p].cov(x);
    down(p);
    if (l <= mid) upd(ls, pl, mid, l, r, x);
    if (r > mid) upd(rs, mid + 1, pr, l, r, x);
    up(p);
}
int query(int p, int pl, int pr, int l, int r){
    if (l > r) return INF;
    if (l <= pl && pr <= r) return t[p].mn;
    down(p);
    int res = INF;
    if (l <= mid) res = min(res, query(ls, pl, mid, l, r));
    if (r > mid) res = min(res, query(rs, mid + 1, pr, l, r));
    return res;
}
void updt(int u, int v, int x){
    while (top[u] != top[v]){
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        upd(1, 1, n, dfn[top[u]], dfn[u], x);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    upd(1, 1, n, dfn[u], dfn[v], x);
}
int qry(int u, int x){
    if (u == x) return t[1].mn;
    if (dfn[x] < dfn[u] || dfn[u] + sz[u] <= dfn[x]) return query(1, 1, n, dfn[u], dfn[u] + sz[u] - 1);
    int v = find2(x, u); // find1(x,u)
    return min(query(1, 1, n, 1, dfn[v] - 1), query(1, 1, n, dfn[v] + sz[v], n));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    rep(i, 2, n){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    rep(u, 1, n) cin >> a[u];
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    cin >> rt;
    while (m--){
        int op, u, v, x;
        cin >> op;
        if (op == 1) cin >> rt;
        else if (op == 2) cin >> u >> v >> x, updt(u, v, x);
        else if (op == 3) cin >> u, cout << qry(u, rt) <<  '\n';
    }
    return 0;
}

:::

P4211 [LNOI2014] LCA

Description

给出一棵以 1 为根的有根树（原题题面为 0-indexed），定义一个点的深度为这个点到根的路径上结点的数量。

2：\begin{bmatrix}1&-\infty&1\\-\infty&-\infty&-\infty\\-\infty&-\infty&0\end{bmatrix}

3：\begin{bmatrix}-\infty&-\infty&-\infty\\-\infty&1&1\\-\infty&-\infty&0\end{bmatrix}

4：\begin{bmatrix}-\infty&-\infty&-\infty\\-\infty&-\infty&-\infty\\-\infty&-\infty&0\end{bmatrix}

初始的状态为 \begin{bmatrix}0&0&0\end{bmatrix}。

进行转移只要把路径上所有的转移矩阵全部乘一遍就行了，最后取所得矩阵 M 的 g_v 即可。

只需要对每一个节点维护一个矩阵，使用线段树维护区间从左到右的乘积 mul1 和从右到左的 mul2 即可。