1、题意
给一颗偶数个节点的有边权树 ， 节点数为n ， 要求划分成n / 2 个集合， 两个点在一个集合中， 代价为两点之间的最短路径 ， 然后要求求最小代价

2、策略
1)、贪心的讲 ， 我们两点之间尽量连一到两条边， 不然多条边肯定会造成更大的代价，
2)、树上的算法一般都是由dfs 为主体框架 ， 来进行构造整个算法流程的
dfs设计的肯定是当前节点u ，儿子节点v之间的关系 ， 同时要所有的关系都要考虑清楚，
一般而言 ， 关系就两种 ， u有儿子节点v ， u没有儿子节点v ，

对于这个问题来说，
第一， 两点之间要连一条边（由两点划分为一个集合， 代价为两点之间的最短路即边权）
那么考虑dfs设计框架关系中第二个关系， u没有儿子节点v ， 即u是叶子节点
对于这个问题，叶子节点u只能连接父亲节点，不然它没有别的边可以用了，
但是如果叶子结点的父亲有偶数个儿子节点， 这偶数个儿子节点必然会全部连接到父亲节点（不然儿子节点没有边可用
图片说明

这个2号节点是4号节点和5号节点的父亲节点， 这个题目要划分两个节点到一块， 现在这种情况一个父亲节点有偶数个孩子节点，并且孩子节点到父亲节点的边全部对答案有贡献， 但是算上父亲节点， 则有奇数个节点，不满组两点划分为一个集合 ，那么这个父亲节点只能向上连接它的父亲节点， 即2号节点连1号节点，
2号节点的孩子几点则相当于两两配对了， 即4号节点和5号节点划分到一个集合中， 2号节点表示无奈，你们不和我连接， 我去找爹爹

相反， 如果2号节点如果有奇数个节点，则2号节点要和全部儿子节点连接
图片说明

此时2 4 5 8 节点自己内部配对了， 并且消耗了三条边， 2号节点就不需要向上连接1号节点了，

由此可以看出来啊，
如果u节点有偶数个孩子节点v ， 即算上u节点有奇数个几点， 那么这个时候就需要u节点向上连接父亲节点，
否则 ， 就可以在u的子树内部自己消化， 不需要算上u到父亲节点的边，

dfs关系中第一种关系u节点有孩子节点v节点， 同样具有同样的性质，
图片说明

这个图 ， 1号节点有偶数个孩子节点， 但是3号节点需要和1号结点连接， 正好划分为（6 ， 7） ， （3 ， 1） ， 2 号子树随便和一个孩子节点连接， 然后两外两个节点划分为一个集合 ，正好划分完
并且题目说明n必定为偶数，满足上图

如果节点u子树***有奇数个节点， 需要连接父亲节点， 贡献加上这个边权， 否则不算

#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 10 ;
vector<pair<int , int>> v[N] ;
int tot[N] , n , m ;
typedef long long ll ;
ll ans = 0 ;
int dfs(int u , int fa , int len)
{
    tot[u] = 1 ;
    for(auto x : v[u]) 
    {

        if(x.first == fa) continue ;
        dfs(x.first , u , x.second) ;
        tot[u] += tot[x.first] ;
    }
    if(tot[u] % 2) ans += len ;
    return 0 ;
}
void work()
{
    int n ;
    cin >> n ;
    ans = 0 ;
    for(int i = 1; i <= n ;i ++) v[i].clear() ;
    for(int i = 1 , x , y , c ; i < n ; i ++) 
          cin >> x >> y >> c , v[x].push_back({y , c }) , v[y].push_back({x , c}) ;
    dfs(1 , 0 , 0) ;
    cout << ans << endl ;
}
int main()
{
    int T ;
    cin >> T ;
    while(T --) 
         work() ;
    return 0 ;
}