C++14(g++5.4) 解法, 执行用时: 1363ms, 内存消耗: 13916K, 提交时间: 2020-04-13 22:45:03

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sc(a) scanf("%d",&a)
#define scc(a,b) scanf("%d%d",&a,&b)
#define ss(a) scanf("%s",&a)
#define CL(a,b) memset(a,b,sizeof(a))
const int maxn=1e5+10;

int n,root;
ll ans,dp[maxn];
struct node
{
	int to;
	ll cost;
};
vector<node> G[maxn];
void dfs(int x,int fa,ll len)
{
	if(len>ans)ans=len,root=x;
	dp[x]=max(dp[x],len);
	for(auto now:G[x])
	{
		int to=now.to;
		ll cost=now.cost;
		if(to==fa)continue;
		dfs(to,x,len+cost);
	}
}
int main()
{
	while(~sc(n))
	{
		for(int i=1;i<=n;i++)G[i].clear(),dp[i]=0;
		for(int i=1;i<=n-1;i++)
		{
			int u,v,c;scc(u,v);sc(c);
			G[u].push_back({v,c});
			G[v].push_back({u,c});
		}
		ans=0;
		dfs(1,-1,0);
		dfs(root,-1,0);
		dfs(root,-1,0);
		ll sum=0;
		for(int i=1;i<=n;i++)
			if(i!=root)sum+=dp[i];
		printf("%lld\n",sum);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1044ms, 内存消耗: 14116K, 提交时间: 2020-02-25 21:06:46

#include<bits/stdc++.h>
using namespace std;
#define N 111111
#define ll long long
#define fi first
#define se second
#define pll pair<int,ll>
#define go(i,a,b) for(int i=a;i<=b;i++)
ll dp[N],mx,ans;
int n,u,v,w,id,id1,id2;
vector<pll>p[N];
void  dfs(int u,int pre,ll w)
{
	dp[u]=max(dp[u],w);
	if(w>=mx) mx=w,id=u;
	for(int i=0;i<p[u].size();i++)
	{
		int v=p[u][i].fi;
		if(v==pre) continue;
		dfs(v,u,w+p[u][i].se);
	}
}
int main()
{
	while(~scanf("%d",&n))
	{
		go(i,1,n) p[i].clear(),dp[i]=0;
		go(i,2,n)
		{
			scanf("%d%d%d",&u,&v,&w);
			p[u].push_back(pll(v,w));
			p[v].push_back(pll(u,w));
			
		}
		ans=mx=0;
		dfs(1,0,0);
		id1=id;mx=0;
		dfs(id1,0,0);
		id2=id,ans+=mx;
		dfs(id2,0,0);
		go(i,1,n)
		{
			if(i==id1||i==id2) continue;
			ans+=dp[i];
		}
		printf("%lld\n",ans);
	}
	return 0;
}