AcWing 1073. 树的中心
给定一棵树,树中包含 n个结点(编号1~n)和 n−1条无向边,每条边都有一个权值。
请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。
5
2 1 1
3 2 1
4 3 1
5 1 1
2
#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;
int n;
int h[N], e[M], w[M], ne[M], idx;
//d1[u] 表示从 u 往下走能到达的最大路径,d2[u] 表示从 u 往下走能到达的次大路径
//p1[u] 表示从 u 出发的最大路径需要经过 u 的儿子节点 j,up[u] 表示从 u 往上走能到达的最大路径
int d1[N], d2[N], p1[N], up[N];
bool is_leaf[N];
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 father)//往上走 返回从 u 往下走能到达的最大路径
{
d1[u] = d2[u] = -INF;//初始化为不可到达
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == father) 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;//仅大于次大值
}
if (d1[u] == -INF)//特判叶子节点
{
d1[u] = d2[u] = 0;
is_leaf[u] = true;
}
return d1[u];
}
void dfs_u(int u, int father)//往下走
{
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == father) continue;
//先判断计算当前链接到的这个子节点往下走的方案
if (p1[u] == j) up[j] = max(up[u], d2[u]) + w[i];//父节点的最大路径经过当前点,则用次大路径比较
else up[j] = max(up[u], d1[u]) + w[i];//否则用最大路径比较
//再递归这个子节点往下
dfs_u(j, u);
}
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs_d(1, -1);
dfs_u(1, -1);
int res = d1[1];
for (int i = 2; i <= n; i ++ )
if (is_leaf[i]) res = min(res, up[i]);//如果是叶子节点 只能往上走
else res = min(res, max(d1[i], up[i]));
printf("%d\n", res);
return 0;
}