Shortest Path

Problem:

一棵树，n个节点（n%2 = 0），问划分成n/2份之后，每份中节点直接距离和加起来最小为多少。

Solution:

由于是一颗有偶数个节点树，所以划分成n/2份，我们可以做到不选取重边，即同一条边不会选取两遍。
对于边的选择与否我们可以通过当前节点是否能和它的儿子选在一起，如果不能，那么它就必须和父亲选在一起，那么在什么情况下它不能和儿子选取在一起呢？
很明显对于一个有a个儿子的节点，如果a为偶数的话，那么这a个节点只有两两配对，如果为奇数的话，那么就可以从a中找出一个与自己配对。
因此求解方法就变成了判断当前节点的儿子节点是否为偶数，是的话就选取当前节点与父亲节点的边，否则，不做操作。

// https://ac.nowcoder.com/acm/problem/13886
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e4 + 10;
ll ans;
int siz[maxn];
struct Node{
    int to,len;
    Node(){}
    Node(int _to,int _len):to(_to),len(_len){}
};
vector<Node> G[maxn];

void dfs(int nowp,int fa,int fa_len){
    siz[nowp] = 1;
    _for(i,0,G[nowp].size()){
        int to = G[nowp][i].to;
        if(to != fa){
            dfs(to,nowp,G[nowp][i].len);
            siz[nowp] += siz[to];
        }
    }
    if(siz[nowp] & 1){ // siz[nowp] & 1 <==> !((siz[nowp] - 1) & 1)
        ans += fa_len;
    }
}
int main(){
    IOS;
    int T,n,u,v,len;
    cin>>T;
    while(T--){
        cin>>n;
        ans = 0;
        rep(i,1,n) G[i].clear();
        rep(i,2,n){
            cin>>u>>v>>len;
            G[u].push_back(Node(v,len));
            G[v].push_back(Node(u,len));
        }
        dfs(1,0,0);
        cout<<ans<<endl;
    } 
    return 0;
}
/**
Problem:
    一棵树，n个节点（n%2 = 0），问划分成n/2份之后，每份中节点直接距离和加起来最小为多少。 
Solution: 
    由于是一颗有偶数个节点树，所以划分成n/2份，我们可以做到不选取重边，即同一条边不会选取两遍。
    对于边的选择与否我们可以通过当前节点是否能和它的儿子选在一起，如果不能，那么它就必须和父亲选在一起，那么在什么情况下它不能和儿子选取在一起呢？
    很明显对于一个有a个儿子的节点，如果a为偶数的话，那么这a个节点只有两两配对，如果为奇数的话，那么就可以从a中找出一个与自己配对。

    因此求解方法就变成了判断当前节点的儿子节点是否为偶数，是的话就选取当前节点与父亲节点的边，否则，不做操作。 

*/