题目：

一棵偶数结点的树，边带权。请将结点分成n/2对点，使每对点路径求和最小。

做法：

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << 
using namespace std;
typedef long long ll;
const int N = 1e4 + 7;
vector<pair<int,int> > g[N];
int mrk[N];
ll dp[N];
void dfs(int u, int p){
    int cnt = 0;//记录u子树中未配对儿子数
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i].first, w = g[u][i].second;
        if (v == p) continue;
        dfs(v, u);//先处理子树v
        dp[u] += dp[v];//v子树的解累加进u子树
        if (!mrk[v]) dp[u] += w, cnt++;//如果结点v在v子树里没下场配对，则v必定在u子树配对，边权加上，cnt++
    }
    if (cnt%2){//未配对儿子奇数，u下场配对
        mrk[u] = 1;//记录u已配对
    }else{
        mrk[u] = 0;//未配对儿子偶数，它们两两配对，u不下场
    }
}
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) g[i].clear();
        memset(mrk, 0, sizeof mrk);
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < n-1; ++i){
            int u, v, w; cin >> u >> v >> w;
            g[u].push_back(make_pair(v, w));
            g[v].push_back(make_pair(u, w));
        }
        dfs(1, 1);
        cout << dp[1] << endl;
    }
    return 0;
}