换根DP:$\mathcal O(n)$
思路与:AcWing 1073. 树的中心 - AcWing 基本一致
- 状态表示
f[i]
:表示以i
为出发点的所有路径的集合,存的是所有路径中路径权值的最大值 [ 即距离点i
的最远的点对应的路径的长度 ]
- 状态计算 —— 集合的划分
确定完根节点之后,从i
点出发的路径可以分为两类:
- 从
i
点往下的路径 - 从
i
点往上到其父节点的路径
f[i]
就是这两类集合各自的最大值,最后再取最值
为了计算这两个集合的最大值,我们维护三个数组:
d1[i]
:从节点i
往下的最长链d2[i]
:从节点i
往下的次长链up[i]
:从节点i
往上的最长链
计算完这三个数组之后,不难发现:f[i] = max(d1[i], up[i])
:从i
往下的最长链和往上的最长链之间的最大值
其中:d1[i]
和d2[i]
与树的直径中的最长链和次长链一致,但是计算up[i]
的时候,我们还需要额外维护一个p1[i]
:表示从节点i
往下的最长链是从哪个点上来的
- 若
j == p1[i]
:说明待遍历的点位于最长链上,此时只能用父节点的次大值d2[i]
更新up[j]
, - 否则
j != p1[i]
:就可以用父节点的最大值d1[i]
更新up[j]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = N << 1; // 无向边
int n;
int h[N], w[M], e[M], ne[M], idx;
int d1[N], d2[N], p1[N], up[N];
/*
1. d1[] 表示以每个节点为根节点的最长链
2. d2[] 表示以 ... 次长链
3. p1[] 存储最长链是从哪个子节点上来的
4. up[] 表示每个节点往上到其父节点的最长路径
*/
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs_d(int u, int fa) // 计算 d1[]、d2[]、p1[] // 自底向上信息
{
d1[u] = d2[u] = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
int d = dfs_d(j, u) + w[i];
if (d >= d1[u])
{
d2[u] = d1[u], d1[u] = d;
p1[u] = j;
}
else if (d > d2[u]) d2[u] = d;
}
return d1[u];
}
void dfs_u(int u, int fa) // 计算 up[] // 自项向下信息
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
if (p1[u] == j) up[j] = max(up[u], d2[u]) + w[i]; // 最长链是从 j 上来的 用次大值更新
else up[j] = max(up[u], d1[u]) + w[i]; // 否则用最大值更新
dfs_u(j, u);
}
}
int main()
{
while (~scanf("%d", &n))
{
idx = 0; // 注意清空!
for (int i = 1; i <= n; i ++ ) h[i] = -1; // 清空表头 // 代替 memset 常数优化
for (int i = 2; i <= n; i ++ )
{
int b, c;
scanf("%d%d", &b, &c);
add(i, b, c), add(b, i, c);
}
dfs_d(1, -1);
dfs_u(1, -1);
for (int i = 1; i <= n; i ++ ) printf("%d\n", max(d1[i], up[i]));
// 每个点到其它点的最远距离 = max(该点往下的最长链, 该点往上的最长距离)
}
return 0;
}
暴力:$\mathcal O(n^2)$
- 枚举每个点作为根节点
- dfs求以该节点为根的最长链
相当于 $n$ 次换根
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = N << 1;
int h[N], w[M], e[M], ne[M], idx;
int n;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int u, int fa) // 返回以 u 为根节点的最长链:O(n)
{
int d1 = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
int d = dfs(j, u) + w[i];
d1 = max(d1, d);
}
return d1;
}
int main()
{
while (scanf("%d", &n) != -1)
{
memset(h, -1, sizeof h);
for (int i = 2; i <= n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(i, a, b), add(a, i, b);
}
for (int i = 1; i <= n; i ++ ) printf("%d\n", dfs(i, -1)); // 分别以每个节点为根
}
return 0;
}