思路分析

非常好的题，通过本题可以学会很多东西

收获一：从任何一个点出发遍历一个图的方法

void dfs_d(int u, int fa){
    for(int i = h[u];i;i = ne[i]){
        int k = v[i];
        if(k == fa) continue;//这里是关键
        dfs_d(k, u);
    }
}

收获二：如何维护从当前节点往下走的第一距离和第二距离

void dfs_d(int u, int fa){
    for(int i = h[u];i;i = ne[i]){
        int k = v[i];
        if(k == fa) continue;
        dfs_d(k, u);
        int d = down1[k] + w[i];
        if(d >= down1[u]){
            down2[u] = down1[u]; 
            down1[u] = d;
        }else if(d > down2[u])
            down2[u] = d;
    }
}

收获三：如何求出从当前节点往上走的最远距离

void dfs_u(int u, int fa){
    for(int i = h[u];i;i = ne[i]){
        int k = v[i];
        if(k == fa) continue;
        if(p[u] == k)
            up[k] = max(up[k], max(down2[u], up[u]) + w[i]);
        else 
            up[k] = max(up[k], max(down1[u], up[u]) + w[i]);
        dfs_u(k, u);
    }
}

下面是完整代码

C++ 代码

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

const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;

int h[N], v[M], ne[M], w[M], idx;
int down1[N], down2[N], up[N];//down1 表示以当前节点为根节点往下走的最远距离，down2表示第二远距离，up表示向上走的最远距离
int p[N];
int n;

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

void dfs_d(int u, int fa){
    for(int i = h[u];i;i = ne[i]){
        int k = v[i];
        if(k == fa) continue;
        dfs_d(k, u);
        int d = down1[k] + w[i];
        if(d >= down1[u]){
            down2[u] = down1[u]; down1[u] = d;
            p[u] = k;
        }else if(d > down2[u])
            down2[u] = d;
    }
}

void dfs_u(int u, int fa){
    for(int i = h[u];i;i = ne[i]){
        int k = v[i];
        if(k == fa) continue;
        if(p[u] == k)
            up[k] = max(up[k], max(down2[u], up[u]) + w[i]);
        else 
            up[k] = max(up[k], max(down1[u], up[u]) + w[i]);
        dfs_u(k, 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) ans = min(ans, max(down1[i], up[i]));

    cout << ans << endl;
    return 0;
}