Shortest Path

其实我们画画图就可以发现，如果把边全部选完，那么一定是有解的。

所以，我们就是删除权值和最多的边，使得原问题还有解。什么是无解呢？就是某个边删除之后，连通块个数为奇数了，那么就不行。

所以直接dfs一次即可，如果当前子树点的个数为偶数个，直接删除即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=N<<1;
int n,sz[N];    long long res;    int head[N],nex[M],to[M],w[M],tot;
inline void ade(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
inline void add(int a,int b,int c){ade(a,b,c);    ade(b,a,c);}
void dfs(int x,int fa){
    sz[x]=1;
    for(int i=head[x];i;i=nex[i])    if(to[i]!=fa){
        dfs(to[i],x);    if(sz[to[i]]%2==0)    res-=w[i];
        sz[x]+=sz[to[i]];
    }
}
inline void solve(){
    cin>>n;    tot=0; memset(head,0,sizeof head); res=0;
    for(int i=1,a,b,c;i<n;i++)    scanf("%d %d %d",&a,&b,&c),res+=c,add(a,b,c);
    dfs(1,1);    cout<<res<<endl;
}
signed main(){
    int T;    cin>>T;    while(T--)    solve();
    return 0;
}