树的最长路径

题目描述

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。
现在请你找到树中的一条最长路径。
换句话说，要找到一条路径，使得使得路径两端的点的距离最远。
注意：路径中可以只包含一个点。

输入格式

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

输出格式

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

数据范围

1≤n≤10000,
1≤ai,bi≤n,
−10^5≤ci≤105

输入样例

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

输出样例

22

题目分析

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long 
const int N=1e4+5;
int h[N],e[2*N],w[2*N],ne[2*N],idx;
int ans;
void add(int x,int y,int z){
	e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
}
int dfs(int u,int f){
	int dist=0,m1=0,m2=0;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		//由于树建立的是无向边，防止回头
		if(j==f)continue;
		//计算该节点向下的路径
		int dis=dfs(j,u)+w[i];
		//不断更新该节点向下的最长路径
		dist=max(dis,dist);
		//更新该节点向下的最长路径和次长路径
		if(dis>m1)m2=m1,m1=dis;
		else if(dis>m2)m2=dis;
	}
	//答案即为每个结点的最长路径和次长路径之和的最大值
	ans=max(ans,m1+m2);
	return dist;
}
signed main(){
	int n,x,y,z;
	cin>>n;
	memset(h,-1,sizeof h);
	for(int i=0;i<n-1;i++){
		cin>>x>>y>>z;
		//建立无向边
		add(x,y,z);
		add(y,x,z);
	}
	dfs(1,-1);
	cout<<ans<<endl;
	return 0;
}