【每日一题】Shortest Path

思路：
题中给定的是一棵树，要求把分成n/2对 让权值最小
看一下范围 在加上是一棵树 所以做法应该是dfs 复杂度为on
直接去考虑贡献
设当前父节点为x 如果x的子树(包括x自己)的大小是个奇数 意味着什么呢
因为要两两配对，那么意味着这奇数个数中，一定有一个数要有外界配对
那么他就一定会经过x到x的父节点的那条边
所以dfs 计算子树的大小 如果子树大小是个奇数，那么对答案有贡献 就要加上父节点往上连接的那一条边

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
ll ans;
struct node
{
    int to;
    ll v;
};
int siz[maxn];
vector<node> e[maxn];
void dfs(int x,int f,ll w){

    for(auto it:e[x]){
        if(it.to==f) continue;
        dfs(it.to,x,it.v);
        siz[x]+=siz[it.to];
    }
    if(siz[x]&1) ans+=w;
}
int main(){
    ios::sync_with_stdio(0);
    int _;cin>>_;
    while(_--){
        int n;cin>>n;ans=0;
        for(int i=1;i<=n;i++) e[i].clear(),siz[i]=1;
        for(int i=1;i<n;i++){
            int x,y,v;cin>>x>>y>>v;
            e[x].push_back({y,v});
            e[y].push_back({x,v});
        }
        dfs(1,0,0);
        cout<<ans<<endl;
    }
}