算法分析

树中的最长路径一定是通过某个点的最大值和次大值之和，那么我们只需要遍历所有点，使用最大值和次大值更新路径。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],w[M],idx;
const int INF=0x3f3f3f3f;
int ans=-INF;
int n;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs(int u,int f) //返回以u往下的最长路径 
{
    int d1=-INF,d2=-INF; //最大值和次大值 
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==f) continue; //往上走的点 
        int d=dfs(j,u)+w[i]; //u经过j这个点往下走的距离 
        if(d>d1) //如果当前距离大于已有最大值 
        {
            d2=d1,d1=d;
        } 
        else if(d>d2) //当前距离小于等于最大值且大于次大值 
        {
            d2=d;
        }
    }
    if(d1==-INF) //没有更新过最大值(叶子节点) 
    {
        d1=0;
    }
    if(d2==-INF) //没有更新过次大值(次大值为0) 
    {
        d2=0;
    }
    ans=max(ans,d1+d2); //更新经过当前点的最长路径 
    return d1; //返回u往下走的最长路径 
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1);
    cout<<ans;
    return 0;
}