https://ac.nowcoder.com/acm/problem/18307

这题是求任意一个城市到另一个城市的最大距离，那么我们就将这类问题抽象为一个树上问题。

求任意两城市的最大路径，不就是求树的直径吗？

所以我们用求树的直径的方法去求任意两城市的最大路径，其实这个最大路径就是树上两个最远的节点。

我们可以从任意节点先dfs一次搜到树的直径的一个端点，然后再dfs一次，搜到的最远的那个节点与当前第一次搜最远的节点之间的路径就是树的直径了。

我使用的是两个数组的树上DP方法。

ac code:

#include<bits/stdc++.h>
using namespace std;
const int N = 23355;
 
struct node{
    int to,w;
};
 
vector<node>arr[N];
 
int d1[N],d2[N];
 
int maxn = 0;
 
int dfs(int u,int father){
    
    for(auto[to,w]:arr[u]){
        if(to==father)continue;
        int d = dfs(to,u)+w;
        if(d>=d1[u])
            d2[u] = d1[u],d1[u] = d;
        else if(d>d2[u])d2[u] = d;
//         cout<<u<<' '<<d1[u]<<' '<<d2[u]<<endl;
        maxn = max(maxn,d1[u]+d2[u]);    //取当前节点向下的最长路径与次长路径的和
//         cout<<d<<' '<<u<<endl;
    }
    return d1[u];
}
 
void solve(){
    int n;cin>>n;
    for(int i = 1;i<n;++i){
        int a,b,c;cin>>a>>b>>c;
        arr[a].push_back({b,c});
        arr[b].push_back({a,c});
    }
    dfs(1,0);
    int ress = 0;
//     cout<<maxn<<endl;
    for(int i = 1;i<=maxn;++i){
        ress += i+10;
    }
    cout<<ress<<endl;
}
int main(){
    solve();
}