算是一题有点思维难度的题。

题意：
有一颗n个节点的树，现在要把这棵树分成n/2部分，每部分都由2个节点构成，给出n-1条边的边权。当2个点构成一个部分的时候，假设是从u->v，认为经过的边的边权和为需要的花费。问最少的花费和是多少。

思路：
一开始的时候有点没有思绪。
但是再纸上画一画可以发现一点特点。我们从叶子节点开始考虑。
假设当前节点为u，他有一个儿子为v，并且v为叶子节点。显然我们直接连接u、v作为一部分，花费为w(u,v)
假设有两个儿子v1,v2,我们需要连接u,v1，此时v2需要和u的父亲相连了。
我们总是以当前节点u作为考虑，可以发现，假设u的一个儿子为v，
如果v子树上的节点为偶数个，v子树自己就可以直接连完了，我们可以省略w(u，v)这条边。
如果v子树上的节点为奇数个，v子树需要有一个点和u相连。
那么我们可以通过dfs计算出当前节点u的和，只需要枚举u的儿子v，如果v子树有偶数个，不需要和u相连直接返回dfs(v)，如果v子树是奇数个，dfs(v)再加一条w(u,v)就好了。

对于点u的儿子个数，我这里先跑了一遍dfs进行计算。
代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10004;
int n;
int tot,head[maxn],son[maxn];
struct node{
    int to,next,w;
}p[maxn*2];
void add(int u,int v,int w){
    tot++;
    p[tot].to=v;
    p[tot].next=head[u];
    p[tot].w=w;
    head[u]=tot;
}
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
    memset(son,0,sizeof(son));
}
int dfs(int x,int fa){
    int ans=1;
    for(int i=head[x];~i;i=p[i].next){
        int y=p[i].to;
        if(y==fa)continue;
        ans+=dfs(y,x);
    }
    return son[x]=ans;
}
long long dfs1(int x,int fa){
    long long ans=0;
    for(int i=head[x];~i;i=p[i].next){
        int y=p[i].to;
        if(y==fa)continue;
        if(son[y]%2==0)ans+=dfs1(y,x);
        else ans=ans+dfs1(y,x)+p[i].w;
    }
    return ans;
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        init();
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,0);
        cout<<dfs1(1,0)<<endl;
    }
    return 0;
}