51nod 1737配对

题意：给定一个n个点的带边权树，  保证n是偶数，给这个树两两配对，使得配对后的点路径和最大，输出最大值。

其实是个很简单的题，但还是被绊了。这充分说明现在连简单题都做不来了555

单独考虑每条边。每个点对答案的贡献就是它被使用的次数乘以权值，而每条边的系数其实是互不影响的，而系数最大值就是它两端的点个数的min，把这个算出来加起来就完了。

为什么这样是对的，即为什么每个系数互不影响，因为完全可以构建一个以重心为中心的菊花图，那样构建完全可以满足每个点系数最大化。

感觉这个思维方式硬伤啊。。多做点题吧。。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define LL long long
inline int read(){
    int x=0,f=1; char a=getchar();
    while(a<'0' || a>'9') {if(a=='-') f=-1; a=getchar();}
    while(a>='0' && a<='9') x=x*10+a-'0',a=getchar();
    return x*f;
}
struct edges{
    int to,v,next;
}e[2*N];
int n,head[N],cnt=1,son[N];
LL ans;
inline void insert(){
    int u=read(),v=read(),c=read();
    e[++cnt]=(edges){v,c,head[u]};head[u]=cnt;
    e[++cnt]=(edges){u,c,head[v]};head[v]=cnt;
}
void dfs(int x,int fa){
    son[x]=1;
    for(int i=head[x];i;i=e[i].next){
        if(e[i].to==fa) continue;
        dfs(e[i].to,x); son[x]+=son[e[i].to];
        ans+=(LL)min(son[e[i].to],n-son[e[i].to])*e[i].v;
    }
}
int main(){
    n=read();
    for(int i=1;i<n;i++) insert();
    dfs(1,0);
    printf("%lld
",ans);
    return 0;
}