简单树形问题

本文对简单的树形问题进行了讲解。

有关树的问题在考试时非常常见，所以必须熟练掌握。本文介绍的问题都比较简单，不涉及什么高难的问题。

树的性质与遍历

我们知道，一棵树有 $n$ 个点， $n-1$ 条边，且一定是连通的。有几种特殊的树：

链：树退化成链式结构。
“菊花图”：树的深度恰好为 $2$ 。

可以简单的使用树的深度优先遍历来解决问题。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, d, ans = 0, dis[100005];
vector <int> G[100005];

void dfs(int o, int f) {
    if (dis[o] <= d && o != 1) ++ans;
    for (int i = 0; i < G[o].size(); ++i) {
        int &y = G[o][i];
        if (y == f) continue;
        dis[y] = dis[o] + 1;
        dfs(y, o);
    }
}

int main(void) {
    scanf("%d%d", &n, &d);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

边权转点权。实际上在树形问题中，边权非常不好处理，所以我们可以在深度优先遍历的时候将边权全放给儿子。大概像这样：

d[y] = w; // 转移边权为儿子的点权
dfs(y, x);

树的直径

指的是树上的最长路径，可以通过两次 DFS 求出。第一次 DFS 从任意节点开始遍历，走到最远的地方，然后从这个地方开始第二次 DFS，走到最远的地方。这两个最远的地方连接起来就是树的直径。

模板，代码如下：

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int n, maxx = 0;
bool v[10005];
int dis[10005];
vector <int> G[10005];

void dfs(int o, int fa) {
    for (int i = 0; i < G[o].size(); ++i) {
        if (G[o][i] == fa) continue;
        dis[G[o][i]] = dis[o] + 1;
        if (dis[G[o][i]] > dis[maxx]) maxx = G[o][i];
        dfs(G[o][i], o);
    }
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v); G[v].push_back(u);
    } dfs(1, -1);
    memset(v, 0, sizeof(v));
    dis[maxx] = 0;
    dfs(maxx, -1);
    printf("%d\n", dis[maxx]);
    return 0;
}

树的直径有一个显然的性质：直径的某个端点到所有点的距离的最小值一定是所有点中最大的。

树的重心

对于树上的每一个点，计算其所有子树中最大的子树节点数，使得这个值最小的点就是这棵树的重心。树的重心有以下性质：

以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

使用反证法。设当前的重心为 $u$ ，与 $u$ 相连的子树 $v$ 的大小超过了整棵树的一半，那么将 $v$ 替换为树的重心，显然这时 $u$ 的子树不超过整棵树大小的一半，而 $v$ 的子树大小减小了 $1$ ，一定比 $u$ 作为重心更好。

树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。

因为如果移动了，增加的距离一定大于等于减少的距离。

把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

如果不在这条路径上，那么只有那个节点的子树的代价会减小，其它的都会增加，得不偿失。

在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

增加或减少一个叶子，只能使最大的子树恰好比一半多 $1$ ，重心只移动 $1$ 即可。

现在我们来看如何求出树的重心。我们假定 $1$ 为根节点，然后设 $size[x]$ 代表 $x$ 的子树大小。我们定义 max_part 为当前 dfs 到的节点中，最大的子树大小。它的孩子们的子树大小在 dfs 时就可以统计，而剩下的一棵子树就是它父亲对应的子树，这就是 $n-size[x]$ 。这样只需要调用一次 dfs，时间复杂度为 $O(n)$ 。

int n, pos, ans = 1e7; // pos 为重心，ans 为重心对应的最大子树
int s[105];
vector <int> G[105];

void dfs(int x, int fa)
{
    s[x] = 1;
    int max_part = 0;
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i];
        if (y == fa) continue; // 想逃回父亲，直接枪毙
        dfs(y, x);
        s[x] += s[y]; // 父节点的子树大小加上子节点的
        max_part = max(max_part, s[y]); // 更新 max_part
    }
    max_part = max(max_part, n - s[x]); // 最后一棵子树是父亲节点对应的子树（这里的子树是指以 x 为根的情况）
    if (max_part < ans) // 答案更优就更新
    {
        ans = max_part;
        pos = x;
    }
}

学过树形 DP 的读者应该可以发现这个东西类似于换根 DP，但又不太一样。

最近公共祖先（LCA）

LCA 是指点集的 LCA，为了方便，我们记某点集 $A=\{u_i|1\leqslant i\leqslant n\}$ 的最近公共祖先为 $LCA(u_1,u_2,\ldots,u_n)$ 或 $LCA(A)$ 。含义是离它们最近的一个点，是它们所有点的祖先。

LCA 有以下性质：

$LCA(u)=u$ ；
$LCA(u,v)=u$ 的充要条件是 $u$ 是 $v$ 的祖先；
如果 $u$ 不为 $v$ 的祖先并且 $v$ 不为 $u$ 的祖先，那么 $u,v$ 分别处于 $LCA(u,v)$ 的两棵不同子树中；
给定一棵二叉树，前序遍历中， $LCA(S)$ 出现在所有 $S$ 中元素之前，后序遍历中 $LCA(S)$ 则出现在所有 $S$ 中元素之后；
两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 $LCA(A \cup B) = LCA(LCA(A),LCA(B))$ ；
两点的最近公共祖先必定处在树上两点间的最短路上，且 $dist(u,v)=h(u)+h(v)-2h(LCA(u,v))$ ，其中 $h(x)$ 指 $x$ 到树根的距离。

这些性质都比较显然，在此不做证明。

现在我们来讨论 LCA 的求法。

LCA 有多种求法，不同情况要用不同的方法。
可以在模板进行测试。

向上标记法

比如我们现在要求 $LCA(u,v)$ ，我们可以先让 $u$ 和 $v$ 向上跳到同一深度，然后让它们一起往上调，一定可以找到它们的 LCA。

int n, m, root;
vector <int> G[500005];
bool v[500005];

struct node {
    int p, fa, dep;
}T[500005];

void dfs(int o, int deep) {
    v[o] = 1; T[o].dep = deep;
    for (int i = 0; i < G[o].size(); ++i)
        if (!v[G[o][i]]) {
            T[G[o][i]].fa = o;
            dfs(G[o][i], deep + 1);
        }
}

int LCA(int x, int y) {
    if (T[x].dep < T[y].dep) swap(x, y);
    while (T[x].dep > T[y].dep) x = T[x].fa; // 跳到同一深度
    if (x == y) return x; // 此处特判可以略去，但习惯写上
    while (x != y) x = T[x].fa, y = T[y].fa; // 一起往上跳
    return x;
}

int main(void) {
    n = read(), m = read(), root = read();
    for (int i = 1; i < n; ++i) {
        int x = read(), y = read();
        G[x].push_back(y); G[y].push_back(x);
    }
    T[root].fa = -1;
    dfs(root, 1); // 构造树
    
    while (m--) {
        int a = read(), b = read();
        cout << LCA(a, b) << endl;
    }
    return 0;
}

树上倍增法

以上做法极慢，最常用的快速求 LCA 的方法是树上倍增法。设 $f[x,k]$ 表示 $x$ 的 $2^k$ 辈祖先。若该节点不存在，则令 $f[x,k]=-1$ （不设为 $0$ 的原因是有的题需要设一个编号为 $0$ 的虚拟节点）。那么有 $f[x,k]=f[f[x,k-1]][k-1]$ ，接下来的思路跟向上标记法大致相同。

在求解 LCA 时，我们先让它们都跳到同一深度。如果此时两个点已经相等，那么这个点就是 LCA（此步不能略去，原因接下来会说明）。然后我们尝试着让它们一起往上跳，如果跳完值还不相等，那一定跳。最后再跳一步即可。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

inline int read(void) {
    int x = 0, c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = (x<<3) + (x<<1) + (c^48), c = getchar();
    return x;
}

int n, m, root;
int dep[500005];
int lg[500005];
int f[500005][20];
vector <int> G[500005];

void dfs(int o, int fa)
{
    f[o][0] = fa; // 根据定义
    dep[o] = dep[fa] + 1; // 深度为父亲 +1
    for (int i = 1; i <= lg[n]; ++i) // 跳出树的值都会变成 -1
        f[o][i] = f[f[o][i - 1]][i - 1];
    for (int i = 0; i < G[o].size(); ++i)
        if (G[o][i] != fa) dfs(G[o][i], o); // 如果不往父亲回，就以 G[o][i] 为儿子，o 为父亲 dfs
}

int LCA(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = lg[n]; i >= 0; --i) // 从一个最大可能值开始枚举，这样做的正确性基于二进制拆分
        if (dep[f[x][i]] >= dep[y]) x = f[x][i]; // 如果跳这么大深度依然比 y 大，那只能跳
    if (x == y) return x; // 此步不能省去，否则已经是 LCA，最后 return 时还会再跳一次
    for (int i = lg[n]; i >= 0; --i)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; // 如果跳这么大都不相等，此时必须要跳
    return f[x][0]; // 最后再跳一步便一定是 LCA
}

int main(void)
{
    scanf("%d%d%d", &n, &m, &root);
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(root, -1); // 让 -1 作为根节点的“父亲“，使得 f 数组中跳出树的都变成 -1
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", LCA(x, y));
    }
    return 0;
}

除了求解 LCA 问题，很多树上问题都会用到树上倍增法。

树上前缀和与差分

前缀和和差分是线性结构上的有力工具，但是它们也可以搬到树上来。

树上前缀和

设 $S_i$ 代表根节点到节点 $i$ 的权值总和，那么：

如果是边权，那么 $d(x,y)=S_x+S_y-2\times S_{LCA(x,y)}$ ，
如果是点权，那么 $d(x,y)=S_x+S_y-S_{LCA(x,y)}-S_{fa[LCA(x,y)]}$ （因为 LCA 处只能减一次）。

树上点差分

也就是对于点权的树上差分。也就是说，给定若干条路经，求出每个点经过的次数。那么：

// s -> t
d[s]++, d[t]++;
d[lca(s, t)]--, d[fa[lca(s, t)]]--;

当然不同的数值也可以改。

模板。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, k, lg[50005], dep[50005];
int f[50005][18], sum[50005];
vector <int> G[50005];

void dfs(int x, int fa)
{
    f[x][0] = fa;
    dep[x] = dep[fa] + 1;   
    for (int i = 1; i <= lg[n]; ++i)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = 0; i < G[x].size(); ++i)
        if (G[x][i] != fa) dfs(G[x][i], x);
}

int LCA(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = lg[n]; i >= 0; --i)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = lg[n]; i >= 0; --i)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

void get(int x, int fa)
{
    for (int i = 0; i < G[x].size(); ++i)
    {
        int y = G[x][i];
        if (y == fa) continue;
        get(y, x);
        sum[x] += sum[y];
    }
}

int main(void)
{
    scanf("%d%d", &n, &k);
    for (int i = 1, u, v; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    dfs(1, 0);
    while (k--)
    {
        int s, t, lca;
        scanf("%d%d", &s, &t);
        lca = LCA(s, t);
        sum[s]++, sum[t]++;
        sum[lca]--, sum[f[lca][0]]--;
    }
    get(1, 0);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, sum[i]);
    printf("%d\n", ans);
    return 0;
}

树上边差分

还是直接将边前缀和搬过来：

d[s]++, d[t]++;
d[lca(s, t)] -= 2;

DFS 序列

树在进行 DFS 时，会有入栈出栈的顺序，而且每一个树恰好入栈一次、出栈一次。这样产生的序列就是树的欧拉序。如果只记录一次节点，那么产生的是 DFS 序，访问到顺序记为时间戳 dfn。

概述

比如这样一棵树：

它的欧拉序就是 1 4 4 2 6 8 8 6 5 5 2 3 7 7 3 1。

可以发现，欧拉序有以下性质：

若树的大小为 $n$ ，那么欧拉序的长度就等于 $2n$ ，每个数恰好出现了两次。
每棵子树 $x$ 在欧拉序中一定是连续的一段，节点 $x$ 一定同时在这个连续段的两端。

而 DFS 序可以与树上差分结合起来，实现满足差分信息的树上信息高效维护。下面我们来看 DFS 序的应用：

单点修改

模板。

单点增加，查询子树和。

根据 DFS 序列的性质，我们可以将树上信息转化到链上来维护。怎么转呢？可以发现，子树一定是在根后面连着的，那么我们记录 $siz$ 大小就可以了。

接下来就是 Fenwick 树了。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#define lowbit(x) (x & -x)

using namespace std;
typedef long long i64;

int n, m, root;
int a[1000005], siz[1000005];
int dfn[1000005], num = 0;
vector <int> G[1000005];

i64 C[1000005];
void add(int x, int k) {
    while (x <= n) {
        C[x] += k;
        x += lowbit(x);
    }
}
i64 sum(int x) {
    i64 res = 0;
    while (x) {
        res += C[x];
        x -= lowbit(x);
    }
    return res;
}

void dfs(int x, int fa) {
    dfn[x] = ++num; siz[x] = 1;
    add(num, a[x]);
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
    }
}

int main(void) {
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(root, 0);
    while (m--) {
        int op, a, x;
        scanf("%d%d", &op, &a);
        if (op == 1) {
            scanf("%d", &x);
            add(dfn[a], x);
        } else {
            printf("%lld\n", sum(dfn[a] + siz[a] - 1) - sum(dfn[a] - 1));
        }
    }
    return 0;
}

子树修改

模板。

子树所有节点增加 $x$ ，子树节点和。

实际上是一样的，我们只需要将树状数组替换为线段树（当然，利用拆分信息树状数组也可以做）。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
typedef long long i64;

int n, m, root;
int a[1000005], siz[1000005];
int dfn[1000005], idx[1000005], num = 0;
vector <int> G[1000005];

i64 T[4000005];
int tag[4000005];

void build(int o, int l, int r) {
    if (l == r) return T[o] = a[idx[l]], void();
    int mid = l + r >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    T[o] = T[o << 1] + T[o << 1 | 1];
}
inline void pushdown(int o, int l, int r) {
    if (!tag[o]) return;
    int mid = l + r >> 1;
    T[o << 1] += 1ll * (mid - l + 1) * tag[o], T[o << 1 | 1] += 1ll * (r - mid) * tag[o];
    tag[o << 1] += tag[o], tag[o << 1 | 1] += tag[o];
    tag[o] = 0;
}
void update(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) return T[o] += 1ll * (r - l + 1) * k, tag[o] += k, void();
    int mid = l + r >> 1; pushdown(o, l, r);
    if (x <= mid) update(o << 1, l, mid, x, y, k);
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k);
    T[o] = T[o << 1] + T[o << 1 | 1];
}
i64 query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o];
    int mid = l + r >> 1; i64 res = 0; pushdown(o, l, r);
    if (x <= mid) res += query(o << 1, l, mid, x, y);
    if (mid < y) res += query(o << 1 | 1, mid + 1, r, x, y);
    return res;
}

void dfs(int x, int fa) {
    dfn[x] = ++num; idx[num] = x; siz[x] = 1; 
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
    }
}

int main(void) {
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(root, 0);
    build(1, 1, n);
    while (m--) {
        int op, a, x;
        scanf("%d%d", &op, &a);
        if (op == 1) {
            scanf("%d", &x);
            update(1, 1, n, dfn[a], dfn[a] + siz[a] - 1, x);
        } else {
            printf("%lld\n", query(1, 1, n, dfn[a], dfn[a] + siz[a] - 1));
        }
    }
    return 0;
}

链上修改

这里简单提一下，有兴趣可以写一下模板。

我们说过，DFS 序维护的依旧是前缀和，所以利用树上差分的方式，配合树状数组可以快速修改与查询，会比重链剖分少一个 $\log$ 。

但是当维护的内容不满足差分的区间可减性，DFS 序就做不了了。

快速 LCA

DFS 序求 LCA 是常用方式中最快的 LCA 算法，并且是在线的。可以做到 $O(n\log n)$ 预处理， $O(1)$ 查询。而欧拉序求 LCA 则有 $2$ 倍的常数，至于利用笛卡尔树的 $O(n)$ 预处理做法则并不使用，因为大部分树上问题都是带 $\log$ 的。尤其是对于虚树这询问 LCA 次数极多的东西，DFS 序的优势很大。

考虑树上的两个节点 $u,v$ 和其 LCA $d$ ， $d$ 显然在 $u,v$ 之前出现。

如果 $u$ 不是 $v$ 的祖先，我们只需要求出 $u$ 和 $v$ 的 DFS 序之间深度最小的一个节点，它的父亲就是 $d$ 。
如果是，那么直接令 $u$ 变成 dfn 比它大 $1$ 的节点，就转化成了上一种情况。

只需要特判掉 $u=v$ ，这样就可以直接改变 $u$ 的 DFS 序了。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

int n, m, root, num, dfn[N], dep[N], lg[N], mi[20][N];
vector<int> G[N];

inline int get(int x, int y) { return dep[x] < dep[y] ? x : y; } // 这个 inline 有用
void dfs(int x, int fa) {
    mi[0][dfn[x] = ++num] = fa, dep[x] = dep[fa] + 1;
    for (int y : G[x]) if (y != fa) dfs(y, x); 
}
int LCA(int u, int v) {
    if (u == v) return u;
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
    int d = lg[v - u];
    return get(mi[d][u + 1], mi[d][v - (1 << d) + 1]);
}

int main(void) {
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    } dfs(root, 0);
    for (int i = 1; i <= lg[n]; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
    for (int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v), printf("%d\n", LCA(u, v));
    return 0;
}

树链与树链剖分

我们学过的很多内容，比如线段树，都只能处理序列，也就是链上的问题。当它跑到了树上，我们还可以使用 DFS 序列来进行处理。但是当维护的信息不满足差分性质后，DFS 序就显得无力了。这是候怎么办？要对树链进行处理了。

概念

我们先简单介绍一下相关概念。

树链是指树上的一条链，树链剖分就是将整棵树剖分成若干条链，使它组合成线性结构，然后可以在线性结构上工作的强大数据结构就可以派上用场了，也简称树剖。

树链剖分有多种形式，比如重链剖分，长链剖分和实链剖分，其中重链剖分最为常用，大部分树剖指的都是它。

这里只介绍最常用的重链剖分，长链剖分请参考《复杂树形问题》。

重链剖分

我们先来看一下这个问题：

你需要写一种数据结构，支持区间修改和区间查询。

这个我当然会！直接线段树敲上去不久完事了嘛！

那么再来一个：

给出一棵树，支持链上修改，链上查询，子树修改，子树查询。

这是什么？

这个题是有的，模板。

我们不会这种题，我们只会在链上做，那就需要使用树链剖分。

重链剖分可以将树上的任意一条路径划分成长度不超过 $O(\log n)$ 的连续链，每条链上的点深度互不相同（即自底向上的一条链，链上所有点的 LCA 为链的深度小的那个端点）。

我们首先需要了解几个概念：

子树的大小：子树中节点的个数。
重子节点（重节点）：表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。
轻子节点（轻节点）：除了重子节点外的所有节点。特别地，树根是轻节点。
重边：连接节点到它的重子节点的边。
轻边：除了重边之外的所有边。
重链：若干条首尾连接的重边，也就是说，一条重链的开头是一个轻节点，剩下的都是重节点。特别地，一个落单的节点也是重链。

这样整棵树就被剖分成若干条重链，可以证明链的规模是 $O(\log n)$ 的。

实现时要通过两次 dfs，大概像这样：

int f[100005], son[100005], top[100005]; // son 指重儿子，没有为 -1；top 指重链的顶端节点的标号
int dep[100005], siz[100005], dfn[100005], tot = 0; // dfn 指时间戳
vector <int> G[100005];

void dfs1(int x, int fa) {
    dep[x] = dep[fa] + 1; f[x] = fa; siz[x] = 1;
    for (int y : G[x])
        if (y != fa) {
            dfs1(y, x); siz[x] += siz[y];
            if (siz[y] > siz[son[x]]) son[x] = y; 
        }
}

void dfs2(int x, int topf) // topf 记录这个重链的顶点
{
    dfn[x] = ++tot; top[x] = topf;
    if (son[x] == -1) return;
    dfs2(son[x], topf); // 优先处理重链
    for (int y : G[x])
        if (y != f[x] && y != son[x]) dfs2(y, y); // 遍历轻儿子
}

注意到重链的处理总是优先的，也就是说，重链内的时间戳编号是连续的，那么就决定了我们维护的时候直接对应了一段序列上的区间。

建立一棵线段树，以 $x$ 到 $y$ 的最短路径上加上 $z$ 为例，像这样：

while (top[x] != top[y]) // 如果它们不在一条重链上
{
    if (dep[top[x]] < dep[top[y]]) swap(x, y); // 要计算深的节点
    update(1, 1, n, dfn[top[x]], dfn[x], z); // 更新
    x = f[top[x]]; // 跳上来，注意重链的头部已经修改过了，跳到重链头的父亲上
}
if (dep[x] > dep[y]) swap(x, y);
update(1, 1, n, dfn[x], dfn[y], z); // 现在已经在一条重链上，更新

发没发现这个处理特别像 LCA 的求解？没错，LCA 确实也可以用树链剖分来求解，但是不如倍增简单，除非恰好这道题目需要用到树链剖分，我们才会使用树链剖分来求解 LCA。

那么对于子树的操作呢？由于是深度优先遍历，所以一棵子树内的时间戳编号也是连续的（依然具有 DFS 序的性质），也可以直接使用线段树维护：

update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, k); // 利用子树的大小直接计算

那么完整代码就很简单了：

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int n, m, root, P;
int w[100005], f[100005], son[100005], top[100005];
int dep[100005], siz[100005], dfn[100005], tot = 0, a[100005];
vector <int> G[100005];

void dfs1(int x, int fa)
{
    dep[x] = dep[fa] + 1; f[x] = fa; siz[x] = 1;
    int maxx = -1;
    for (auto y : G[x])
        if (y != fa)
        {
            dfs1(y, x);
            siz[x] += siz[y];
            if (siz[y] > maxx) son[x] = y, maxx = siz[y];
        }
}

void dfs2(int x, int topf)
{
    dfn[x] = ++tot; top[x] = topf; a[tot] = w[x];
    if (son[x] == -1) return;
    dfs2(son[x], topf);
    for (auto y : G[x])
        if (y != f[x] && y != son[x]) dfs2(y, y);
}

int T[400005], tag[400005];
inline void maintain(int o) { T[o] = (T[o << 1] + T[o << 1 | 1]) % P; }
inline void pushdown(int o, int l, int r)
{
    if (!tag[o]) return;
    int mid = l + r >> 1, ls = o << 1, rs = o << 1 | 1;
    tag[ls] = (tag[ls] + tag[o]) % P, tag[rs] = (tag[rs] + tag[o]) % P;
    T[ls] = (T[ls] + 1ll * tag[o] * (mid - l + 1)) % P, T[rs] = (T[rs] + 1ll * tag[o] * (r - mid)) % P;
    tag[o] = 0;
}
void build(int o, int l, int r)
{
    if (l == r) {
        T[o] = a[l] % P;
        return;
    }
    int mid = l + r >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    maintain(o);
}
void update(int o, int l, int r, int x, int y, int k)
{
    if (x <= l && r <= y) {
        T[o] = (T[o] + 1ll * k * (r - l + 1)) % P;
        tag[o] = (tag[o] + k) % P;
        return;
    }
    pushdown(o, l, r);
    int mid = l + r >> 1;
    if (x <= mid) update(o << 1, l, mid, x, y, k);
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k);
    maintain(o);
}
int query(int o, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr) return T[o];
    pushdown(o, l, r);
    int mid = l + r >> 1, res = 0;
    if (ql <= mid) res = (res + query(o << 1, l, mid, ql, qr)) % P;
    if (mid < qr) res = (res + query(o << 1 | 1, mid + 1, r, ql, qr)) % P;
    return res;
}

int main(void)
{
    memset(son, 0xff, sizeof(son));
    scanf("%d%d%d%d", &n, &m, &root, &P);
    for (int i = 1; i <= n; ++i) scanf("%d", w + i);
    for (int i = 1, u, v; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs1(root, 0);
    dfs2(root, root);
    build(1, 1, n);
    while (m--)
    {
        int k, x, y, z;
        scanf("%d", &k);
        if (k == 1)
        {
            scanf("%d%d%d", &x, &y, &z);
            z %= P;
            while (top[x] != top[y])
            {
                if (dep[top[x]] < dep[top[y]]) swap(x, y);
                update(1, 1, n, dfn[top[x]], dfn[x], z);
                x = f[top[x]];
            }
            if (dep[x] > dep[y]) swap(x, y);
            update(1, 1, n, dfn[x], dfn[y], z);
        }
        else if (k == 2)
        {
            scanf("%d%d", &x, &y);
            int ans = 0;
            while (top[x] != top[y])
            {
                if (dep[top[x]] < dep[top[y]]) swap(x, y);
                ans = (ans + query(1, 1, n, dfn[top[x]], dfn[x])) % P;
                x = f[top[x]];
            }
            if (dep[x] > dep[y]) swap(x, y);
            ans = (ans + query(1, 1, n, dfn[x], dfn[y])) % P;
            printf("%d\n", ans);
        }
        else if (k == 3)
        {
            scanf("%d%d", &x, &k);
            update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, k);
        }
        else
        {
            scanf("%d", &x);
            printf("%d\n", query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1));
        }
    }
    return 0;
}

算法理论实践复杂度为 $O(n\log^2 n)$ ，但实际上远远达不到上界，重链剖分的常数很小。

但即使如此，树链剖分也是比 DFS 序慢的。如果能使用 DFS 序，更推荐用它。

树链剖分求 LCA

之前维护链的过程很像求 LCA 往上跳的过程，所以重链剖分也可以用来求 LCA。

int LCA(int x, int y) {
    while (top[x] != top[y]) { // 不在一条重链上
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

一般来讲树链剖分会比倍增算法快一点，常数也很小（想想那个二维数组吧），甚至不会比 $O(1)$ LCA 慢（因为有寻址）。

Problemset

我们来看一些有趣的题目，前面的一些题目都很简单，后面的部分题目相当复杂。