树的最长路径

1072. 树的最长路径

给定一棵树，树中包含 n 个结点（编号1~n）和 n?1 条无向边，每条边都有一个权值。
现在请你找到树中的一条最长路径。
换句话说，要找到一条路径，使得使得路径两端的点的距离最远。
注意：路径中可以只包含一个点。
输入格式
第一行包含整数 n。
接下来 n?1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。
输出格式
输出一个整数，表示树的最长路径的长度。
数据范围
1≤n≤10000,
1≤ai,bi≤n,
?105≤ci≤105
输入样例：
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;
struct eg{
    int v,c,nex;
}edge[N*2];
int head[N],cnt,ans,Maxl[N];
void addedge(int u,int v,int c){
    edge[cnt]=(eg){v,c,head[u]};
    head[u]=cnt++;
}
void dfs(int u,int pre){
    int Max1=0,Max2=0;
    for(int i=head[u];~i;i=edge[i].nex){
        int v=edge[i].v, c=edge[i].c;
        if(v==pre) continue;
        dfs(v,u);
        int t=Maxl[v]+c;
        if(t>Max1) Max2=Max1,Max1=t;
        else if(t>Max2) Max2=t;
    }
    Maxl[u]=Max1;
    ans=max(ans,Max1+Max2);
}
int main(){
    int n;
    memset(head,-1,sizeof head);
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v,c;
        cin>>u>>v>>c;
        addedge(u,v,c);
        addedge(v,u,c);
    }
    dfs(1,0);  
    cout<<ans<<endl;
    return 0;
}

树的最长路径

原文：https://www.cnblogs.com/jjl0229/p/12652331.html