蓝桥杯2013年第四届真题-大臣的旅费

解题思路:求树的直径,在使用等差数列的前n项和得出答案.

因为全为正数所以可以跑两边最长路就可以求出,此处给出树上dp
参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int to;
	int w;
	int next;
}mp[1000005];
int head[500005];
int cnt=0;
void add(int a,int b,int c)
{
	mp[++cnt].next=head[a];
	mp[cnt].to=b;
	mp[cnt].w=c;
	head[a]=cnt;
}
int dp[500005];
int money=0;
void dfs(int u,int fa)
{
	for(int i=head[u];i;i=mp[i].next)
	{
		int v;
		v=mp[i].to;
		if(v==fa)continue;
		dfs(v,u);
		money=max(money,dp[u]+dp[v]+mp[i].w);
		dp[u]=max(dp[u],dp[v]+mp[i].w);
		
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	dfs(1,0);
	//cout<<money;
	printf("%lld",(long long)(10*money+money*(money+1)/2));
}