图论——树上问题 学习笔记
目录
树的直径
定义
树上任意两节点之间最长的简单路径即为树的直径。
显然，一棵树可以有多条直径，他们的长度相等。
性质
- 若树上所有边边权均为正，则树的所有直径有交，且中点重合；
- 有树的直径 \((p,q)\)，则距离任意点 \(x\) 最远的点一定为 \(p\) 或 \(q\)；
- 树的直径的中点到其他所有点的最大距离最小（详见下面，树的中心）；
- 两个树的一条直径分别为 \((s_1,t_1)\) 和 \((s_2,t_2)\)，把这两个树通过一条边合并成一棵大树，大树直径的两个端点必在 \(s_1,t_1,s_2,t_2\) 中取，共有 \(\binom{4}{2}=6\) 种情况；
- 两个树的直径分别为 \(\ell_1,\ell_2\)，把这两个树直径的中点相连，新生成的树直径最小，且新直径长度为 \(\max\{\ell_1,\ell_2,\lceil\ell_1/2\rceil+\lceil\ell_2/2\rceil+1\}\)。
求解：两遍 DFS
仅适用于，边权非负；否则贪心不成立。
- 从任意点 \(x\) 出发，找到树上距离点 \(x\) 最远的点 \(p\)；
- 从点 \(p\) 出发，找到树上距离点 \(p\) 最远的点 \(q\)；
- 则 \((p,q)\) 为该树的直径。
证明：见 OI-Wiki。
拓展：求方案，记录每个点的父亲是谁，然后从 \(q\) 一步步推到 \(p\) 就行了。
求解：树形 DP
定理：树上每条链 \((s,t)\) 都可以拆成两条直链 \((s,\text{lca}(s,t))+(t,\text{lca}(s,t))\)；感性理解。
那么，对于每个点 \(x\)，就可以求出以这个点为 \(\text{lca}\) 的直径，即这个点下面的最长链和次长链 \((m_1,m_2)\)，即可合并为以点 \(x\) 为 \(lca\) 的直径；最终取最大值即可。
拓展：求方案，记录每个点是由哪个点转移来，以及找到直径时的 \(\text{lca}\) 点 \(x\)。
代码
\(\text{Solution }1\)：https://www.luogu.com.cn/record/128564207
vector<int> g[N]; int c, d[N];
void dfs(int u, int fa) {
for (int v : g[u])
if (v != fa) { if ((d[v] = d[u] + 1) > d[c]) c = v; dfs(v, u); }
} inline int solve() {
d[1] = 0, c = 1; dfs(1, -1);
d[c] = 0; dfs(c, -1);
return d[c];
} // 两遍 DFS
\(\text{Solution }2\)：https://www.luogu.com.cn/record/128565162
vector<int> g[N]; int res;
int dfs(int u, int fa) { // 返回以 u 为 lca 的树的直径
int m1 = 0, m2 = 0; for (int v : g[u]) {
if (v == fa) continue;
int d = dfs(v, u) + 1;
if (d >= m1) m2 = m1, m1 = d;
else if (d >= m2) m2 = d;
} res = max(res, m1 + m2); return m1;
} int solve() {
res = 0; dfs(1, 0); return res;
} // 树形 DP
题目
实测第一种方法略慢，因为要跑两遍 DFS；但是第一种方法更方便记录方案。
模板题：SP1437、U283565；应用题：CF455C (Civilization)。
树的重心
定义
对无根树，每个点 \(x\) 的子树定义为：删去 \(x\) 后所形成的各个连通块；最大子树最小的点称为树的重心。
性质
- 树的重心最多只有两个，且如果有两个，则它们相邻；
- 重心的所有子树大小都不超过整棵树大小的一半；
- 重心到树上所有点的距离和最小，如果有两个重心，则到它们的距离和相等；
- 插入或删除一个叶子，树的重心的位置最多移动一个点；
- 用一条边连接两棵树，新的数的重心在连接原来两棵树的重心的路径上；
- 一棵树的重心一定在根节点所在的重链上。
求解：树形 DP
树形 DP，然后卡定义，枚举找最大子树最小的点。
代码
\(\text{Problem }1\)：https://www.luogu.com.cn/record/128573058
vector<int> g[N]; int n, sz[N], mc[N], mx;
void dfs(int u, int fa) {
sz[u] = 1; for (int v : g[u]) if (v != fa) {
dfs(v, u), sz[u] += sz[v], mc[u] = max(mc[u], sz[v]);
} mc[u] = max(mc[u], n - sz[u]), mx = min(mx, mc[u]);
} void solve() {
mx = 2e9; dfs(1, -1);
for (int i = 1; i <= n; ++i) if (mc[i] == mx) printf("%d", i);
} // 输出所有重心
\(\text{Problem }2\)：https://www.luogu.com.cn/record/128579397
vector<int> g[N]; int n, sz[N], mc[N], r;
void dfs(int u, int fa) {
sz[u] = 1; for (int v : g[u]) if (v != fa) {
dfs(v, u), sz[u] += sz[v], mc[u] = max(mc[u], sz[v]);
} mc[u] = max(mc[u], n - sz[u]);
if (mc[u] < mc[r] || (mc[u] == mc[r] && u < r)) r = u;
} void solve() {
r = 0, mc[0] = 2e9; dfs(1, -1); printf("%d\n%d\n", r, mc[r]);
} // 输出重心及其最大子树大小
题目
模板题：U104609、U164672；应用题：P1670 (Tree Cutting)。
树的中心
定义
所有节点中，到树中其他节点的最远距离最小的节点，叫树的中心。
性质
性质即定义，到树中其他节点的最远距离最小。
求解：树的直径
分析定义，你会发现与上面树的直径的性质 \((3)\) 一模一样。
证明：一棵树上到点 \(x\) 最远的点一定是其直径 \((S,T)\) 的一个端点，根据三角不等式 \(\text{dis}(S,x)+\text{dis}(x,T)\ge\text{dis}(S,T)\)，所以 \(\max\{\text{dis}(S,x),\text{dis}(x,T)\}\ge\frac{1}{2}\text{dis}(S,T)\)，而等号是在 \(x\) 为 \((S,T)\) 中点是取到。
然后就可以用树的直径求解了。注意这里要记录路径信息（中点难道不是路径上的吗），因此可以用 \(\text{Solution }1\) 更加方便，虽然速度不是最优的。
求解：树形 DP
又要 \(\text{down}\) 又要 \(\text{up}\) 的，两遍 DFS 居然还不一样？太麻烦不想写。
可以借鉴：https://www.cnblogs.com/Liuz8848/p/11726834.html
代码
\(\text{Solution }1\)：https://www.luogu.com.cn/record/128591860
vector<int> g[N];
int c, d[N], f[N];
void dfs(int u, int fa) {
for (int v : g[u])
if (v != fa) { if ((d[v] = d[u] + 1) > d[c]) c = v; f[v] = u; dfs(v, u); }
} void solve() {
d[1] = 0, c = 1; dfs(1, -1);
d[c] = 0, f[c] = -1; dfs(c, -1);
int len = d[c] + 1, lc = len >> 1;
int q = c; for (int i = 1; i < lc; ++i) q = f[q];
if (len & 1) printf("%d", f[q]);
else printf("%d %d", min(q, f[q]), max(q, f[q]));
} // 树的直径
\(\text{Solution }2\)：https://www.luogu.com.cn/record/128592255
int dfs_down(int u, int fa) {
down1[u] = down2[u] = -INF;
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i]; if (v == fa) continue;
int d = dfs_down(v, u) + 1;
if (d > down1[u]) down2[u] = down1[u], down1[u] = d, p[u] = v;
else if (d > down2[u]) down2[u] = d;
} if (down1[u] == -INF && down2[u] == -INF) down1[u] = down2[u] = 0;
return down1[u];
} void dfs_up(int u, int fa) {
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i]; if (v == fa) continue;
if (p[u] == v) up[v] = max(up[u], down2[u]) + 1;
else up[v] = max(up[u], down1[u]) + 1;
dfs_up(v, u);
}
} void solve() {
dfs_down(1, 0), dfs_up(1, 0);
int res = INF; vector<int> ans;
for (int i = 1; i <= n; ++i) {
int t = max(down1[i], up[i]);
if (t == res) ans.push_back(i);
else if (t < res) res = t, ans.clear(), ans.push_back(i);
} for (int i : ans) printf("%d ", i);
} // 树形 DP
经典问题１：最小化最大距离
问题简述
来源：P5536 核心城市。
从一个 \(n\) 个点的树中选出相邻的 \(k\) 个点（ \(k\le n\) ），使未被选出的点，到这个被选出来的块，最大距离最小。
求解：树的中心
考虑 \(k=1\) 的情况，显然这是树的中心的模板题。
拓展到 \(k>1\) 的情况，显然树的中心依旧要取，因为如果不取树的中心，树的直径的端点 \((S,T)\) 到任意一个点的距离都 \(>\frac{1}{2}\text{dis}(S,T)\)。
因此，我们先选择直径中点，然后提根。
下一个选谁？选根的儿子中，子树最深的那个；因为如果它没有被选，那么它的儿子们也不能被选，那么到已选城市的距离最大值始终不会减小。然后，以此类推，每次都选一个子树最深的。
最大距离是多少？显然是未被选出的点中，最大的子树深度 \(-1\)。
总结：提树的中心为根，选择子树深度最大的 \(k\) 个，然后最小的最大距离为，子树深度第 \(k+1\) 大的子树深度 \(-1\)。
有代码：
int c, a[N];
int d[N], f[N];
void dfs(int u, int fa) {
for (int v : g[u]) if (v != fa) {
d[v] = d[u] + 1, f[v] = u; dfs(v, u);
if (d[v] > d[c]) c = v;
}
} void dfk(int u, int fa) {
for (int v : g[u]) if (v != fa)
dfk(v, u), a[u] = max(a[u], a[v] + 1);
} int solve() {
c = 1, d[1] = 1; dfs(1, -1);
d[c] = 1; dfs(c, -1);
int lc = d[c] >> 1; for (int i = 1; i <= lc; ++i) c = f[c];
dfk(c, -1); sort(a + 1, a + 1 + n, greater<int>());
return a[k + 1] + 1;
} // P5536 核心城市
Reference
[1] https://oi-wiki.org/graph/tree-diameter/
[2] https://oi-wiki.org/graph/tree-centroid/