NC13886

题意

给你一颗n(偶数）结点的树，将其分为n/2对，求所有对数相连的路径之和最小为多少？

思路

DFS 数据结构
既然是图论那就先画图吧在这里插入图片描述
左图由于以2号结点为根节点的子树结点数(包括其自身)为3（奇数），那么显然这棵树上一定有个节点要从树外找一个节点相连，那么必须要经过2号结点与其父节点的这条路(2->1)。
右图告诉我们如果能偶数配对的子树则不需要相连。
叶子节点为子树的结点数一定为1显然一定会加上。
DFS求子树的结点数，若结点数为奇数则需要该节点与其父节点相连的这一条边，若为偶数则不需要。

注意：多组数据要每次清空vector数组，然后置于cnt数组不需要memset是因为dfs里面一开始都会赋过1，所以无影响。

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e4 + 5;

ll res,n,cnt[N];
vector<P> G[N];

void dfs(ll u,ll fa,ll cost){
    cnt[u]=1;
    for(auto c:G[u]){
        ll x=c.fi,y=c.se;
        if(x==fa) continue;//若为父节点当然不做啦
        dfs(x,u,y);//递归求子树的节点数量
        cnt[u]+=cnt[x];
    }
    if(cnt[u]&1) res+=cost;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>n;int t=n-1;res=0;
        for(int i=1;i<=n;i++) G[i].clear();
        while(t--){
            ll u,v,w;
            cin>>u>>v>>w;
            G[u].push_back(P(v,w));
            G[v].push_back(P(u,w));
        }
        dfs(1,-1,0);
        cout<<res<<'\n';
    }
    return 0;
}