C++11(clang++ 3.9) 解法, 执行用时: 86ms, 内存消耗: 9336K, 提交时间: 2019-04-14 20:25:30

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int,LL> pr; 

const int MAX_N=1e5+5;
int n;
LL ans;
LL M1[MAX_N],M2[MAX_N];
vector<pr> e[MAX_N];

void DFS(int u,int pre);
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	int u,v,w;
	for(int i=1;i<n;++i)
	{
		//Warning: v点不一定为子节点
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	DFS(1,0);
	cout<<ans<<endl;
	
	return 0;
}

void DFS(int u,int pre)
{
	M1[u]=-1e16;	M2[u]=0;
	int v,w;
	for(auto c:e[u])
		if(c.first!=pre){
			v=c.first;	w=c.second;
			DFS(v,u);
			ans=max(ans,M1[u]+M2[v]+w);
			ans=max(ans,M2[u]+M1[v]+w);
			M1[u]=max(M1[u],M2[v]+w);
			M2[u]=max(M2[u],M1[v]+w);
		}
}

C++14(g++5.4) 解法, 执行用时: 118ms, 内存消耗: 10200K, 提交时间: 2019-04-15 15:43:05

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>p;
vector<p>g[100005];
long long m1[100005],m2[100005];
long long ans;
void dfs(int u,int fa){
	m1[u]=-1e16,m2[u]=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].first,w=g[u][i].second;
		if(v==fa)
			continue;
		dfs(v,u);
		ans=max(ans,m1[u]+m2[v]+w);
		ans=max(ans,m2[u]+m1[v]+w);
		m1[u]=max(m1[u],m2[v]+w);
		m2[u]=max(m2[u],m1[v]+w);
	}
}
int main(){
	int n;
	scanf("%d",&n);
	int u,v,w;
	for(int i=0;i<n-1;i++){
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	ans=0;
	dfs(1,0);
	printf("%lld\n",ans);	
}