目录

信竞学习笔记：树上问题初步

发表于
更新于
40 4.0~5.2 分钟 1817

本文主要介绍一些树的性质和基础树上问题的解法。

树的存储

树可以看作一个无向图进行存储。定义一个 vector<int/edge> 类型的数组。我们先介绍无边权的树：

vector<int> g[N];

向图中添加一条 u 和 v 之间的无向边：

g[u].push_back(v);
g[v].push_back(u);

要遍历与 u 相连的所有的边，可以做这样的遍历：

for (const int &v : g[u]) {
    // ...
}

对于有边权的树，我们可以定义一个结构体存储边的另一个端点和边权：

struct edge {
    int to, w;
};

同理，定义数组、增加边和遍历与某一节点相连的所有边如下：

vector<edge> g[N];

void addedge(int u, int v, int w) {
    g[u].push_back({v, w});
    g[v].push_back({u, w});
}

void findall(int u) {
    for (const edge &e : g[u]) {
        int v = e.to, w = e.w;
        // ...
    }
}

树的遍历

例题：P5908

树的遍历和图的遍历类似，通常使用 DFS 或 BFS。

遍历树（存储时无向）的 DFS 通常一定有两个参数：u 和 fa。u 代表遍历到的当前节点，fa 代表当前节点的父节点（不能往回走）。于是，我们可以写出一个基本的 DFS 代码（下面均以无权图为例）：

void dfs(int u, int fa) {
    for (const int &v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        // ...
    }
}

也可以使用 BFS。BFS 使用队列实现，队列中存储的是节点编号和可能的其他信息。核心代码如下：

void bfs() {
    queue<int> q;
    q.push(1); // 注：某些题目中根节点不一定为 1
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // ...
        for (const int &v : g[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            // ...
            q.push(v);
        }
    }
}

树的重心

例题：P1395

树的重心是指，以这个节点为根节点，所有子树中最大的子树最小。重心一个性质：树中所有节点到一个固定节点的距离之和中，到重心的距离是最小的。

树的重心可以用 DFS 求解。具体地说，对于一个节点 u，在 DFS 的过程中计算它所有子树的大小的和 size_u 和最大子树的大小 f_u。在 DFS 时求解这两个值。当以 u 为根节点时，u 还有一个子树大小为 n - size_u，则 f_u = \max\{f_u, n - size_u\}。最后，与当前记录的重心 center 比较，如果 f_u < f_{center}，center \leftarrow u。

树的直径

例题：B4016

树的直径是指树上最长的不重复经过一个点的路径长度。树的直径有一个重要的性质：距离树上任意一个节点最远的节点一定是树的直径的一个端点。

我们可以用两遍 DFS 法求解直径：先从任意一个端点出发，进行一遍 DFS，找到最远端点 far。再从 far 出发，进行一遍 DFS，找到最远端点 u，此时 u 和 far 就是直径的两个端点。

我们还可以使用树形 DP 求解树的直径。对于每个节点，求解其到每个属于其子树的叶子结点的最长路径 len_u，用 dp_u 代表在以 u 为根节点的子树中，经过点 u 的最长路径。则遍历到 u 的子节点 v 时，len_u 表示 v 前面所有子树中求得的到叶子结点的最长路径，len_v 表示 v 以下到叶子结点的最长路径，故可得：

dp_u = \max\limits_{v \in son_u} \{len_u + len_v + 1\}

随后，在对于每个 v 更新 dp_u 后更新 len_u：

len_u = \max\limits_{v \in son_u} \{len_v + 1\}

最后在所有的 dp_u 中取最大值，即为树的直径。核心代码如下：

void dfs(int u, int fa) {
    for (const int &v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        dp[u] = max(dp[u], len[u] + len[v] + 1);
        len[u] = max(len[u], len[v] + 1);
    }
    ans = max(ans, dp[u]);
}

最近公共祖先（LCA）

例题：P3379

最近公共祖先（LCA）问题是一类求解树上任意两个节点距离两个节点距离和最近（层数更深）的公共祖先节点的问题。

倍增法是常用的求 LCA 的做法。要求 LCA，首先应该将两个节点深度保持一致，为此需要将更深的节点提升上来。如果此时二者还不一致，则要使两个节点同步提升，直到找到 LCA。暴力的做法是一格一格的往上跳，效率很低。为此，我们采用倍增思想优化。

预处理是 anc_{i,j} 代表第 i 个节点向上 2^j 层的祖先节点。每次跳 2 的次方个节点，这样可以大幅提升效率。先从大的提升幅度开始尝试，再尝试小的。这一方面是为了保证效率，一方面，先小后大未必能保证答案正确性。基于二进制的特性，这种方式一定能找到 LCA。

预处理部分如下，时间复杂度 O(n \log n)：

void dfs(int u, int fa) {
    for (const int &v : g[u]) {
        if (v == fa) continue;
        d[v] = d[u] + 1;
        anc[v][0] = u; // 2^0 = 1
        dfs(v, u);
    }
} 

void pre_anc() { // 递推地预处理出祖先节点
    for (int j=1; j<=18; j++) {
        for (int i=1; i<=n; i++) {
            anc[i][j] = anc[anc[i][j-1]][j-1]; // 2^{j-1} * 2^{j-1} = 2^j
        }
    }
}

查找 LCA 的函数如下，最坏时间复杂度 O(\log n)：

int LCA(int u, int v) {
	if (d[u] < d[v]) swap(u, v); // 使 u 为更深的节点
	for (int i=18; i>=0; i--) {
		if (d[anc[u][i]] >= d[v]) {
			u = anc[u][i]; // 提升 u
		}
	} 
	if (u == v) return u; // u, v相同，意味着找到了
	for (int i=18; i>=0; i--) {
		if (anc[u][i] != anc[v][i]) { // == 可能会跳过
			u = anc[u][i], v = anc[v][i];
		}
	}
	return anc[u][0]; // anc[u][0] == anc[v][0] 时不会提升，所以要在返回时提升
}

树上差分

例题：P3128

我们知道，对于一个线性序列，差分思想可以帮助我们快速进行区间修改。同样，在树上进行区间修改操作，我们同样可以维护差分序列，这就称作树上差分。

令 LCA(u,v) 为 u 和 v 两个节点的最近公共祖先；对于节点 x，fa(x) 为其父节点（代码中可以利用 LCA 的预处理数组表示为 anc[x][0]）。维护数组 p 为差分数组，p_u - p_{fa(u)} 即是节点 u 的点权。

要使 u 到 v 的路径上每个元素都增加 1，可以将这条路径视作由 u 到 LCA(u,v) 和 v 到 LCA(u,v) 两部分组成。由于 LCA(u,v) 被重复计算，故这个节点上的点权要额外减 1。和线性序列类似，我们将 p_u 和 p_v 增加 1，并令 p_{LCA(u,v)} 和 p_{fa(LCA(u,v))} 分别减少 1。最后遍历整棵树，利用前缀和还原差分数组，让每个节点的权值加上其父节点，即

p_u = \left( \sum\limits_{v \in son_u} p_v \right) + p_u.

后统计答案即可。

求 LCA 可以使用前面讲过的倍增法解决。以下是本题 DFS 求前缀和数组的代码：

void dfs2(int u, int fa) {
    for (const int &v : g[u]) {
        if (v == fa) continue;
        dfs2(v, u);
        p[u] += p[v];
    }
    ans = max(ans, p[u]); 
}