1、題意
給一顆偶數(shù)個節(jié)點的有邊權(quán)樹 ， 節(jié)點數(shù)為n ， 要求劃分成n / 2 個集合， 兩個點在一個集合中， 代價為兩點之間的最短路徑 ， 然后要求求最小代價

2、策略
1)、貪心的講 ， 我們兩點之間盡量連一到兩條邊， 不然多條邊肯定會造成更大的代價，
2)、樹上的算法一般都是由dfs 為主體框架 ， 來進行構(gòu)造整個算法流程的
dfs設計的肯定是當前節(jié)點u ，兒子節(jié)點v之間的關(guān)系 ， 同時要所有的關(guān)系都要考慮清楚，
一般而言 ， 關(guān)系就兩種 ， u有兒子節(jié)點v ， u沒有兒子節(jié)點v ，

對于這個問題來說，
第一， 兩點之間要連一條邊（由兩點劃分為一個集合， 代價為兩點之間的最短路即邊權(quán)）
那么考慮dfs設計框架關(guān)系中第二個關(guān)系， u沒有兒子節(jié)點v ， 即u是葉子節(jié)點
對于這個問題，葉子節(jié)點u只能連接父親節(jié)點，不然它沒有別的邊可以用了，
但是如果葉子結(jié)點的父親有偶數(shù)個兒子節(jié)點， 這偶數(shù)個兒子節(jié)點必然會全部連接到父親節(jié)點（不然兒子節(jié)點沒有邊可用

這個2號節(jié)點是4號節(jié)點和5號節(jié)點的父親節(jié)點， 這個題目要劃分兩個節(jié)點到一塊， 現(xiàn)在這種情況一個父親節(jié)點有偶數(shù)個孩子節(jié)點，并且孩子節(jié)點到父親節(jié)點的邊全部對答案有貢獻， 但是算上父親節(jié)點， 則有奇數(shù)個節(jié)點，不滿組兩點劃分為一個集合 ，那么這個父親節(jié)點只能向上連接它的父親節(jié)點， 即2號節(jié)點連1號節(jié)點，
2號節(jié)點的孩子幾點則相當于兩兩配對了， 即4號節(jié)點和5號節(jié)點劃分到一個集合中， 2號節(jié)點表示無奈，你們不和我連接， 我去找爹爹

相反， 如果2號節(jié)點如果有奇數(shù)個節(jié)點，則2號節(jié)點要和全部兒子節(jié)點連接

此時2 4 5 8 節(jié)點自己內(nèi)部配對了， 并且消耗了三條邊， 2號節(jié)點就不需要向上連接1號節(jié)點了，

由此可以看出來啊，
如果u節(jié)點有偶數(shù)個孩子節(jié)點v ， 即算上u節(jié)點有奇數(shù)個幾點， 那么這個時候就需要u節(jié)點向上連接父親節(jié)點，
否則 ， 就可以在u的子樹內(nèi)部自己消化， 不需要算上u到父親節(jié)點的邊，

dfs關(guān)系中第一種關(guān)系u節(jié)點有孩子節(jié)點v節(jié)點， 同樣具有同樣的性質(zhì)，

這個圖 ， 1號節(jié)點有偶數(shù)個孩子節(jié)點， 但是3號節(jié)點需要和1號結(jié)點連接， 正好劃分為（6 ， 7） ， （3 ， 1） ， 2 號子樹隨便和一個孩子節(jié)點連接， 然后兩外兩個節(jié)點劃分為一個集合 ，正好劃分完
并且題目說明n必定為偶數(shù)，滿足上圖

如果節(jié)點u子樹***有奇數(shù)個節(jié)點， 需要連接父親節(jié)點， 貢獻加上這個邊權(quán)， 否則不算

#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 ;
}