学步园

题意：给出一棵树，求找出一点到所有点的交通能力最大，交通能力是路径上的最小边的权值。

思路：记得前几天我们做了这个比赛的题目，当时这题好像没看。自己加了长春的现场赛，发现这题想通了还挺简单的，我们把边排序，从大到小加边，我们可以计算每棵树内选点的最大距离，树的节点数。两个树合并时，考虑在哪个集合选点可以最大化就可以了。

#pragma comment(linker, "/STACK:1024000000,1024000000")  
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int N=201000;
int f[N],son[N];
__int64 dis[N];
struct edge
{
	int st,ed,w;
}e[N];
int cmp(void const *a,void const *b)
{
	edge *c,*d;
	c=(edge *)a;
	d=(edge *)b;
	return d->w-c->w;
}
int find(int a)
{
	if(a!=f[a])
		f[a]=find(f[a]);
	return f[a];
}
int main()
{
	int i,n,x,y;
	__int64 w,a,b;
	while(scanf("%d",&n)!=-1)
	{
		for(i=0;i<n-1;i++)
			scanf("%d%d%d",&e[i].st,&e[i].ed,&e[i].w);
		for(i=1;i<=n;i++)
		{f[i]=i;son[i]=1;dis[i]=0;}
		qsort(e,n-1,sizeof(e[0]),cmp);
		for(i=0;i<n-1;i++)
		{
			x=find(e[i].st);
			y=find(e[i].ed);
			//一棵树不会出现x==y的情况
			w=e[i].w;
			a=dis[x]+son[y]*w;//在x集合中选点
			b=dis[y]+son[x]*w;//在y集合中选点
			if(a>=b)
			{
				dis[x]=a;
				f[y]=find(x);
				son[x]+=son[y];
			}
			else
			{
				dis[y]=b;
				f[x]=find(y);
				son[y]+=son[x];
			}
		}
		printf("%I64d\n",dis[find(1)]);
	}
	return 0;
}