算法分析

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

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int ans=-INF;
typedef pair<int,int> PII;
#define x first
#define y second
vector<PII> g[N];
int n;
int dfs(int u,int f) //返回以u往下的最长路径 
{
	int d1=-INF,d2=-INF; //最大值和次大值 
	for(auto k:g[u])
	{
		int j=k.x;
		if(j==f) continue; //往上走的点 
		int d=dfs(j,u)+k.y; //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;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	dfs(1,-1);
	cout<<ans;
	return 0;
}