每日一题

自己看的别人的题解才看懂的！#*
这个题的题意是让我们把一颗树，分为两个部分，每个部分内部之间的路权值最小。

首先我们来看任一个节点，如果这个节点下面的子树(包含当前节点)是奇数的话，那么我们就应该把这个节点与他的父节点之间的边连接，因为我们如果不添加的话，我们这颗子树下面必然要有一个匹配不成功。
比如我们用2号节点举例子，2号节点有三个儿子，其中三个儿子没有子节点，那么就那么这三个节点应该练2号节点，此时2号节点有四个孩子（包括它本身）那么我们就不用再把2号节点连接到1号节点了以此类推....

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
typedef long long ll;
const int N = 1e4 + 10 + 1e4;
int tot,T,head[N],ne[N],ver[N],edge[N],n;
using namespace std;
int si[N];
ll res ;
void dfs(int u ,int fa,int len)
{
    si[u] = 1;
    for(int i = head[u] ; i ; i = ne[i])
    {
        int v = ver[i], w = edge[i];
       // printf("%d->%d->%d\n",u,v,w);
        if(v != fa){
            dfs(v,u,w);
            si[u] += si[v];
        }
    }
    if(si[u] & 1) res = res + 1ll * len;
}
void add(int u ,int v ,int w)
{
    ver[++tot] = v,edge[tot] = w;
    ne[tot] = head[u],head[u] = tot;
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        memset(head,0,sizeof(head));
        memset(ne,0,sizeof(ne));
        memset(si,0,sizeof(si));
        tot = 0;
        res = 0;
        scanf("%d",&n);
        for(int i = 0 , u ,v ,w ;i < n - 1; i++)
        {
            scanf("%d %d %d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,0,0);
        printf("%lld\n",res);
    }
    return 0;
}