这道题其实是codeforces一道题的简化版本。
这里放一下cf的题目链接：https://codeforces.ml/contest/1281/problem/E

思路与题解

由于是计算边的贡献，我们可以关注某一条边是否需要被计算在内。
如何考虑呢？ 容易知道当某一条边的子树中如果有偶数个节点，那么这些点可以内部配对，也就是说不需要考虑这条边的贡献。反之，如果这条边的子树中有奇数个节点，那么必定有一个点会连出来，这条边的贡献就会+1。并且要最小的画，这条边的贡献就是1。(cf还要求算最大的贡献，可以思考）

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define ll long long
#define LLMax LLONG_MAX
#define LLMin LLONG_MIN
#define PII pair<int,int>
#define Max INT_MAX
#define Min INT_MIN
#define FOR1(i,a,b) for(int i=(a);i<(b);i++)
#define FOR2(i,a,b) for(int i=(a);i<=(b);i++)
#define DWN(j,b,a) for(int j=(b);j>=(a);j--) 
#define SET0(a) memset(a,0,sizeof(a))
#define SET1(a) memset(a,-1,sizeof(a))
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int INF=0x3f3f3f3f;
const int NINF=-INF-1;
const double PI=acos(-1); 
const int mod=1e9+7;
const int maxn=3e6+5;
using namespace std;

int n, T;
vector<PII> G[maxn];
ll sz[maxn], ans;

void dfs(int rt, int fa, int val)
{
    if(G[rt].size() == 1 && rt != 1){
        ans += G[rt][0].second;
        sz[rt] = 1;
        return;
    }    
    for (int i = 0; i < G[rt].size(); i ++){
        if(G[rt][i].first == fa) continue;
        dfs(G[rt][i].first, rt, G[rt][i].second);
        sz[rt] += sz[G[rt][i].first];
    }
    if(++sz[rt] & 1) ans += val;
}

int main()
{
    IOS;
    cin >> T;
    while(T --)
    {
        cin >> n;
        for (int i = 1; i < n; i ++)
        {
            int a, b, w;  cin >> a >> b >> w;
            G[a].push_back({b, w});
            G[b].push_back({a, w});
        }
        ans = 0;
        SET0(sz);
        dfs(1, 0, 0);
        //cout << sz[1] << " "  << sz[2] << " " << sz[3] << endl;
        cout << ans << endl;

        for(int i = 1; i <= n; i ++) G[i].clear();
    }
    return 0;
}