1073. 树的中心

给定一棵树，树中包含 n 个结点（编号1~n）和 n?1 条无向边，每条边都有一个权值。

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。

输入格式

第一行包含整数 n。

接下来 n?1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。

输出格式

输出一个整数，表示所求点到树中其他结点的最远距离。

数据范围

1≤n≤10000,
1≤ai,bi≤n,
1≤ci≤105

输入样例：

5 
2 1 1 
3 2 1 
4 3 1 
5 1 1

输出样例：

2

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int h[N], e[N], ne[N], w[N], idx;
int n;
int st[N];
int d1[N], d2[N], p[N], up[N];void add(int a, int b, int c)
{e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}int dfs_down(int u)
{st[u] = 1;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (st[j])continue;int dist = dfs_down(j) + w[i];if (dist > d1[u])d2[u] = d1[u], d1[u] = dist, p[u] = j;else if (dist > d2[u])d2[u] = dist;}return d1[u];
}void dfs_up(int u)
{st[u] = 1;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (st[j])continue;if (p[u] == j)up[j] = max(up[u], d2[u]) + w[i];elseup[j] = max(up[u], d1[u]) + w[i];dfs_up(j);}
}
int main()
{cin >> n;memset(h, -1, sizeof(h));for (int i = 1; i < n; i++){int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}memset(st, 0, sizeof(st));dfs_down(1);memset(st, 0, sizeof(st));dfs_up(1);int res = 0x3f3f3f3f;for (int i = 1; i <= n; i++){res = min(res, max(d1[i], up[i]));}cout << res << endl;return 0;
}