算法1

(树形DP)

一道经典的树形DP的题目，首先最直观的思路就是求距离每个点最远的点是什么？然后再求min一下就可以了。
所以关键是距离每个点最远的点有哪些，如何求？

• 求子树的最大距离 - 即向下的远的点
• 求父亲的距离最远的点 - 即向上的最远的点

求子树的最远距离，可以用上一题的思路来做。
求父亲的最远距离，要判断一下是否经过当前子节点

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, M = 2 * N, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], up[N], p[N];
int n, ans = INF;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dfs_u(int u, int father) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        int d = dfs_u(j, u) + w[i];
        if (d > d1[u]) {
            d2[u] = d1[u], d1[u] = d, p[u] = j;
        }
        else if (d > d2[u]) d2[u] = d;
    }
    //printf("%d %d %d\n", u, d1[u], d2[u]);
    return d1[u];
}

void dfs_f(int u, int father) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        if (p[u] != j) {
            up[j] = max(d1[u], up[u]) + w[i];
        }
        else if (p[u] == j) {
            up[j] = max(up[u], d2[u]) + w[i];
        }
        dfs_f(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_u(1, -1);
    dfs_f(1, -1);
    for (int i = 1; i <= n; i ++) {
        //printf("%d %d %d %d\n", i, d1[i], d2[i], up[i]);
        int temp = max({d1[i], up[i]});
        ans = min(ans, temp);
    }
    cout << ans << endl;

    return 0;
}