题意：给定一个n个点的带边权树， 保证n是偶数，给这个树两两配对，使得配对后的点路径和最大，输出最大值。
其实是个很简单的题，但还是被绊了。这充分说明现在连简单题都做不来了555
单独考虑每条边。每个点对答案的贡献就是它被使用的次数乘以权值，而每条边的系数其实是互不影响的，而系数最大值就是它两端的点个数的min，把这个算出来加起来就完了。
为什么这样是对的，即为什么每个系数互不影响，因为完全可以构建一个以重心为中心的菊花图，那样构建完全可以满足每个点系数最大化。
感觉这个思维方式硬伤啊。。多做点题吧。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define LL long long 5 inline int read(){ 6 int x=0,f=1; char a=getchar(); 7 while(a<‘0‘ || a>‘9‘) {if(a==‘-‘) f=-1; a=getchar();} 8 while(a>=‘0‘ && a<=‘9‘) x=x*10+a-‘0‘,a=getchar(); 9 return x*f; 10 } 11 struct edges{ 12 int to,v,next; 13 }e[2*N]; 14 int n,head[N],cnt=1,son[N]; 15 LL ans; 16 inline void insert(){ 17 int u=read(),v=read(),c=read(); 18 e[++cnt]=(edges){v,c,head[u]};head[u]=cnt; 19 e[++cnt]=(edges){u,c,head[v]};head[v]=cnt; 20 } 21 void dfs(int x,int fa){ 22 son[x]=1; 23 for(int i=head[x];i;i=e[i].next){ 24 if(e[i].to==fa) continue; 25 dfs(e[i].to,x); son[x]+=son[e[i].to]; 26 ans+=(LL)min(son[e[i].to],n-son[e[i].to])*e[i].v; 27 } 28 } 29 int main(){ 30 n=read(); 31 for(int i=1;i<n;i++) insert(); 32 dfs(1,0); 33 printf("%lld\n",ans); 34 return 0; 35 }
原文：http://www.cnblogs.com/enigma-aw/p/6275197.html