$\LARGE\color{orange}{刷题日记(算法提高课)}$

我们需要找到某个点，使得该点距离其他点的最远距离最近

也就是我们求出每个点到其余点的最远距离，最后遍历所有点得到最小值即可

对于某个点 $u$ 而言，经过的路径有三种可能：

• 该路径的一个端点在以 $u$ 为根的子树中，另一个端点为 $u$ 本身

• 该路径的两个端点均在以 $u$ 为根的子树中

• 该路径的一个端点在以 $u$ 为子树的根中，另一个在 $u$ 的上方

也就是说，对于节点 $u$ 而言，既可以向下走也可以向上走

对于前面两种情况，我们参考 AcWing 1072. 树的最长路径 的做法，求出每个点向下的最大距离 $d1[u]$ 和次大距离 $d2[u]$ ，这样便得到 $u$ 往下走的最大距离

下面我们考虑向上走的情况，即遍历到 $u$ 的父节点 $fu$

由于 $u$ 到 $fu$ 的距离是固定的，因此我们需要考虑 $fu$ 到其余点的最大路径

如果这条最大路径经过了 $u$ ，我们需要用 $fu$ 的次大路径来更新 $u$ 往上走的路径长度 $up[u]$

如果这条路径没有经过 $u$ ，我们直接用 $fu$ 的最大路径来更新 $u$ 往上走的路径长度 $up[u]$

完整代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e4 + 10, M = 2 * N, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int n, d1[N], d2[N], up[N], p1[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(j == p1[u]) 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 = 1; 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 ans = INF;
    for(int i = 1; i <= n; i++)
        if(is_leaf[i]) ans = min(ans, up[i]);//如果是叶子节点，那么只能用往上走的路径更新
        else ans = min(ans, max(d1[i], up[i]));//如果不是叶子节点，那么往上往下的路径需要用来更新
    cout << ans << endl;
    return 0;
}