Solution

由题意可知是一个树形结构。若要使两两之间边权最小，尽量不能选重边，也就是说尽可能在节点所在子树里寻找答案。

显然与叶子节点相连的边必须选。然后考虑其他边：

• 若一棵子树中的节点有偶数个，那么两两配对即可，不用添加新的边权。
• 若一棵子树有奇数个节点，那么根节点要和其他子树连边，所以还要加上根节点与其父节点之间的边的边权。

综上， 统计子树大小，偶数不用处理，奇数加边权即可。

数据范围较大，注意开 。

时间复杂度： 。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=1e4+10;
struct edge{
    ll t,v,w;
}e[maxn<<1];
ll T,n,tot,ans,hd[maxn];
void add(ll x,ll y,ll z){
    tot++;
    e[tot].t=hd[x];
    e[tot].v=y;
    e[tot].w=z;
    hd[x]=tot;
}
ll Dfs(ll u,ll fa,ll x){
    ll cnt=1;
    for(int i=hd[u];i!=0;i=e[i].t)
        if(e[i].v!=fa)
            cnt+=Dfs(e[i].v,u,e[i].w);
    if(cnt%2)
        ans+=x;
    return cnt;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>T;
    ll x,y,z;
    while(T--){
        memset(hd,0,sizeof(hd));
        ans=tot=0;
        cin>>n;
        for(int i=1;i<n;i++){
            cin>>x>>y>>z;
            add(x,y,z);
            add(y,x,z);
        }
        Dfs(1,0,0);
        cout<<ans<<endl;
    }
    return 0;
}