1 问题
给定一棵无向无权树,对每个节点
可用 CSES · Tree Distances I 检验实现,节点从
在 换根DP:距离和 中,可以从总和里减去一棵子树的贡献;最大值没有这样的减法。给孩子传递信息时,需要另外解决排除这个孩子自身贡献的问题。
2 内外划分
先以
| 状态 | 含义 |
|---|---|
两个状态都允许停在
任意目标节点都在子树内或子树外,所以:
3 向下的距离
要走向
孩子先于父亲计算即可。这里一个孩子提供的贡献是
4 向上的距离
对孩子
- 停在
,后续距离为 。 - 继续往
的父亲方向走,后续距离由 提供。 - 进入另一个孩子
的子树,后续距离为 ,要求 。
因此:
不能直接使用
图中,
5 最大与次大
若对每个孩子都重新扫描其他孩子,一颗星形树就会产生
| 信息 | 含义 |
|---|---|
| 最大孩子贡献,与 |
|
| 排除一个最大贡献来源后,剩余孩子的最大贡献,与 |
|
| 提供当前最大贡献的孩子编号 |
给孩子
second 表示不同孩子提供的第二份贡献,不是严格小于最大值的下一个数值。如果两个孩子都贡献
代码按孩子编号记录最大值来源。遇到与最大值相等的新贡献时,仍然可以更新次大值。没有其他孩子时,次大值保留为
如果只存最大值,排除其来源后直接退回
6 手算示例
沿用图中的六节点树:边为
| 节点 | 最大来源 |
||||
|---|---|---|---|---|---|
| 1 | 3 | 2 | 2 | 0 | 3 |
| 2 | 2 | 0 | 3 | 3 | 3 |
| 3 | 1 | 0 | 4 | 4 | 4 |
| 4 | 0 | 0 | 无 | 5 | 5 |
| 5 | 1 | 0 | 6 | 4 | 4 |
| 6 | 0 | 0 | 无 | 5 | 5 |
例如,给
7 正确性
第一遍按后序计算。任何向子树内部的路径,都唯一属于停在本点或进入某个孩子的情况,取最大值便得到正确的
第二遍中,孩子子树外的目标节点,按路径从父节点出发的下一方向,分为父节点自身、父亲方向和其他孩子方向。转移完整覆盖了这三类,并排除了重新进入当前孩子的非法路径,因此得到正确的
父亲先于孩子处理,所有外部状态都能依次求出。最后将内部与外部取最大值,就是全树最远距离。
8 代码实现
与上一篇相同,先记录父亲先于孩子的顺序,倒序计算向下信息,再正序计算向上信息,避免长链递归。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
vector<int> g[maxn];
int fa[maxn], order[maxn];
int down[maxn], second[maxn], from[maxn], up[maxn], ans[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
order[1] = 1;
int total = 1;
for (int i = 1; i <= total; ++i) {
int u = order[i];
for (int v : g[u]) {
if (v == fa[u]) continue;
fa[v] = u;
order[++total] = v;
}
}
// 第一遍:保存不同孩子提供的最大、次大贡献,允许两者数值相等。
for (int i = total; i >= 1; --i) {
int u = order[i];
for (int v : g[u]) {
if (v == fa[u]) continue;
int value = down[v] + 1;
if (value > down[u]) {
second[u] = down[u];
down[u] = value;
from[u] = v;
} else if (value > second[u]) {
second[u] = value;
}
}
}
// 第二遍:向孩子传递不经过它自身子树的最远距离。
for (int i = 1; i <= total; ++i) {
int u = order[i];
ans[u] = max(down[u], up[u]);
for (int v : g[u]) {
if (v == fa[u]) continue;
int other = (from[u] == v ? second[u] : down[u]);
up[v] = 1 + max(up[u], other); // 先到 u,再向父亲方向或兄弟子树走
}
}
for (int u = 1; u <= n; ++u) {
cout << ans[u] << (u == n ? '\n' : ' ');
}
return 0;
}
每个节点只扫描邻接表常数次,时间复杂度为 int 即可。
9 非负边权
若边长非负,将孩子的贡献改为
最大、次大、向上距离和答案都要使用足够大的类型,通常为 long long。排除孩子的逻辑保持不变,仍按贡献来源区分。上述以
10 直径与中心
无权树上也可以先求 树的直径 的两个端点
树的中心最小化最远距离;树的重心 控制删除节点后各连通块的大小,二者定义不同。
11 相关题解
暂无相关题解