【每日一题】Shortest Path

题意：n个点的一棵树，选出n/2个点对，使得点对之间两点距离之和最小，n保证偶数
sum[i]是以结点i包括结点i的子树结点个数，当sum[i]为偶数时，只需要让这颗子树中的点两两相连，代价就是该子树的所有边；当sum[i]为奇数时，就需要另外一个点与外面(即除这颗子树外)的点相连，最优当然是选择这颗子树的根，这时这颗子树的根与它的父节点相连的这条边就会对答案贡献

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
struct Edge{
    int to,nex;
    ll w;
}e[N*2];
ll ans;
int n,head[N],idx;
int sum[N];
void addedge(int u,int v,ll w){
    e[idx].to = v;
    e[idx].nex = head[u];
    e[idx].w = w;
    head[u] = idx++;
}
int dfs(int u,int fa,ll w){
    sum[u] = 1;
    for(int i = head[u];~i;i = e[i].nex){
        int v = e[i].to;
        if(v == fa) continue;
        sum[u]+=dfs(v,u,e[i].w);
    }
    if(sum[u]&1) ans+=w;
    return sum[u];
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(head,-1,sizeof(head));
        idx = 0;
        for(int i = 1;i < n;i++){
            int u,v;ll w;
            scanf("%d%d%lld",&u,&v,&w);
            addedge(u,v,w);addedge(v,u,w);
        }
        ans = 0;    
        dfs(1,-1,0);
        printf("%lld\n",ans);
    }
    return 0;
}