AcWing1073 - 数的中心

给定一棵树，树中包含 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 <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
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) {
  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;
}