AcWing 1072. 树的最长路径

给定一棵树，树中包含 n个结点(编号1-n)和 n−1条无向边，每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说，要找到一条路径，使得使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

输入格式
第一行包含整数 n。

接下来 n−1行，每行包含三个整数 ai,bi,ci，表示点 ai和 bi之间存在一条权值为 ci的边。

输出格式
输出一个整数，表示树的最长路径的长度。

数据范围
1≤n≤10000,1≤ai,bi≤n,−10^5≤ci≤10^5

6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

22

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

const int N=10010,M=N << 1;
int w[N],h[N],e[N],ne[N],idx;
int ans;

void add(int a,int b,int c)
{
    e[idx]=b;//记录该节点链接到的节点
    w[idx]=c;//边权
    ne[idx]=h[a];//将上次的头节点往下压
    h[a]=idx++;//更新单链表的头节点
}

int dfs(int u,int father)
{
    int dist=0;// 表示从当前点往下走的最大长度
    int d1=0,d2=0;//最大子树路径与次大子树路径

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];//取连接到的点
        if(j == father) continue;
        //d是 该节点从当前点往下走的最大长度+链接到头节点u的边权 的总和
        int d=dfs(j,u)+w[i];
        dist=max(dist,d);

        if(d >= d1) d2=d1,d1=d;//更新最大子树路径
        else if(d > d2) d2=d;//更新次大
    }

    ans=max(ans,d1+d2);//以ans形式传给main

    return dist;
}

int main()
{
    int n;
    cin>>n;

    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)//n-1条无向边
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    dfs(1,-1);//任意一个节点当作根

    cout<<ans<<endl;
}