Shortest Path

题意：将n个点分成n/2个集合 问最小代价是多少

思路：通过画图可以发现，当某个结点的子树结点个数（包括它本身）个数为偶数的话，他是可以实现内部互联的，反之，如果点为奇数的话，它肯定要和外边的点相连，所该点到父亲结点的一定会有贡献

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 10010;

struct node
{
    int w;
    int to;
    int next;///相同起点的上一次加入的边的存储位置 (指向下一条边在edge数组中的位置)
} edge[N << 1];

int cnt,n,m;///边的编号
int head[N];///以i为起点最近加入一条边的位置
int sz[N];

void addEdge(int u,int v,int w)
{
    edge[cnt].w = w;
    edge[cnt].to = v;///边的终点
    edge[cnt].next = head[u];///head[u]:上一次加入的边的位置
    head[u] = cnt ++ ;///更新以u为起点的最新加入的边的编号
}

LL res = 0;

void dfs(int u,int fa,int w)
{
    sz[u] = 1;

    for(int i = head[u] ; ~i ; i = edge[i].next)
    {
        int to = edge[i].to;

        if(to == fa)
            continue;

        dfs(to,u,edge[i].w);

        sz[u] += sz[to];
    }

    if(sz[u]%2 == 1)
        res += w;
}

void init()
{
    for(int i = 0; i < N; i ++)
        head[i] = -1;
    cnt = 0;
    res = 0;
    memset(sz,0,sizeof sz);
}

int main()
{
    int t;
    scanf("%d",&t);

    while(t --)
    {
        scanf("%d",&m);
        init();

        for(int i = 0;i < m - 1;i ++)
        {
            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            addEdge(u,v,w);
            addEdge(v,u,w);
        }

        dfs(1,0,0);

        printf("%lld\n",res);
    }

    return 0;
}