【问题描述】
azui大爷厌倦了每天在家颓废的生活，于是开始打工送快递。Jeremy同学不想让azui大爷太轻松，于是想让他送快递的路程尽可能的长。
一句话来说就是：
给出一棵n个点的树，将这n个点两两配对，求所有可行的方案中配对两点间的距离的总和最大为多少。
【输入格式】
一个数n（1<=n<=100,000,n保证为偶数）
接下来n-1行每行三个数x,y,z表示有一条长度为z的边连接x和y（0<=z<=1,000,000,000）
【输出格式】
一个数表示答案。
【样例输入】
6
1 2 1
1 3 1
1 4 1
3 5 1
4 6 1
【样例输出】
7
【样例解释】
（1，2）（3，4）（5，6）分别配对
【数据范围】
对于20%的数据，n <= 14
对于另20%的数据，所给的树是一条链。
对于100%的数据，n <= 100000
#include<iostream> #include<cstdio> using namespace std; typedef long long LL; const int N=1e5+5; int n, fa[N], fir[N], ecnt; struct node{ int e, w, next; }edge[N<<1]; LL ans, pcnt[N]; void Getin( int &shu ) { char c; int f=1; shu=0; for( c=getchar(); c<'0' || c>'9'; c=getchar() ) if( c=='-' ) f=-1; for( ; c>='0' && c<='9'; c=getchar() ) shu=shu*10+c-'0'; shu*=f; } void Link( int s, int e, int w ) { edge[ ++ecnt ].e=e; edge[ecnt].w=w; edge[ecnt].next=fir[s]; fir[s]=ecnt; edge[ ++ecnt ].e=s; edge[ecnt].w=w; edge[ecnt].next=fir[e]; fir[e]=ecnt; } void Dfs( int s ) { pcnt[s]=1; for( int i=fir[s]; i; i=edge[i].next ) if( edge[i].e!=fa[s] ){ fa[ edge[i].e ]=s; Dfs( edge[i].e ); pcnt[s]+=pcnt[ edge[i].e ]; } } int main() { Getin(n); for( int i=1; i<n; i++ ) { int a, b, c; Getin(a); Getin(b); Getin(c); Link( a, b, c ); } Dfs(1); for( int s=1; s<=n; s++ ) for( int i=fir[s]; i; i=edge[i].next ) if( fa[ edge[i].e ]==s ) ans+=min( pcnt[ edge[i].e ], n-pcnt[ edge[i].e ] )*edge[i].w; printf( "%lld\n", ans ); return 0; } /* 一条边断开后图被分为s1, s2两部分 用边的权值乘上min(s1,s2)即是答案 */