【每日一题】4月3日

注意到每对点一定是在某一个点（它们的lca）处合并。
于是可以dp。设 表示已经处理完了 的子树 当前是否剩余一个还没有配对的点（实际上等价于 的奇偶性）。
转移合并两个子树的时候考虑一下要不要两边的点配个对就好了。

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 5e5 + 5;

struct Edge{
    int to,w,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,w,head[v]};head[v] = cnt;
}

int f[MAXN][2],n;

inline void merge(int x,int y,int w){// x <- y
    int t0 = f[x][0],t1 = f[x][1];
    f[x][0] = std::min(t0+f[y][0],t1+f[y][1]+w);
    f[x][1] = std::min(t1+f[y][0],t0+f[y][1]+w);
}

inline void dfs(int v,int fa=0){
    f[v][0] = 1e9;f[v][1] = 0;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dfs(e[i].to,v);
        merge(v,e[i].to,e[i].w);
    }
}

inline void Solve(){
    scanf("%lld",&n);std::fill(head,head+n+1,0);cnt = 0;
    FOR(i,2,n){
        int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
    }
    dfs(1);
    printf("%lld\n",f[1][0]);
}

signed main(){
    int T;scanf("%lld",&T);
    while(T--) Solve();
    return 0;
}