题面

Today HH becomes a designer, and he faces a problem so he asks you for help.
Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities.
HH the designer is going to design a plan to divide n city into n/2 pairs so that the sum of the length between the n/2 pairs city is minimum.
Now HH has finished it but he doesn't know whether it's true so he ask you to calculate it together.
It's guaranteed that n is even.

题解

今天的题很简单啊~
首先我们仔细观察一下样例2，可以发现我们好像不论怎么选择 所得到的解都是所有边的权值和。那什么情况下能减少这个最终答案呢？观察样例1，很容易看出来当一条边的两边的点数都为偶数时，那这条边就不需要被选择了。
所以我们先统计一下所有边的和，然后dfs枚举看哪条边满足上述条件，那么对应的答案减掉这条边的权值就可以啦！！

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

//head
struct Ed{
    int to,w,next;
}edge[maxn];
int tot,head[maxn],sz[maxn];
void add(int u,int v,int w){
    edge[++tot]={v,w,head[u]};
    head[u]=tot;
}


int t,n;
LL ans;
void dfs(int u,int fa){
    sz[u]=1;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to,w=edge[i].w;
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if((n-sz[v])%2==0&&(sz[v]%2==0)) ans-=w;
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
         scanf("%d",&n);
         ans=0;tot=0;
         for(int i=1;i<=n;i++) head[i]=0;
         for(int i=1,u,v,w;i<n;i++){
             scanf("%d%d%d",&u,&v,&w);
             add(u,v,w);
             add(v,u,w);
             ans+=w;
         }
         dfs(1,-1);
         printf("%lld\n",ans);
    }
}