题意：给出一棵有偶数的节点的树，将其分成n/2对点，并且要求n/2对点的路径之和最小

思路：树上任意两点间的距离是唯一的，题目又要求路径之和最小，所以选择两个节点，要么是父节点和其孩子节点，要么是父节点的两个孩子节点，还有一种情况是多了一个孩子节点，那么肯定要先加上到父节点的距离，然后再和另外一个节点配对。
所以在树上dfs，枚举子树的节点个数，一颗子树如果节点个数为偶数，就不需要再添加节点配对，如果节点个数为奇数，需要和父节点往外的一个节点配对，那么答案就要加上这颗子树到父节点的距离

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
struct node
{
    int t, w, next;
} edge[maxn << 1];
int n, cnt;
int head[maxn], tot[maxn];
ll ans;
void add(int x, int y, int z)
{
    edge[++cnt].t = y;
    edge[cnt].w = z;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
void dfs(int x, int fa, int len)
{
    tot[x] = 1;
    for (int i = head[x]; ~i; i = edge[i].next)
    {
        int y = edge[i].t;
        if (y == fa)
            continue;
        dfs(y, x, edge[i].w);
        tot[x] += tot[y];
    }
    if (tot[x] % 2 == 1)
        ans += len;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ans = 0, cnt = 0;
        scanf("%d",&n);
        memset(head, -1, sizeof(head));
        memset(tot, 0, sizeof(tot));
        for (int i = 1; i <= n - 1; ++i)
        {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            add(x, y, w);
            add(y, x, w);
        }
        dfs(1, 0, 0);
        printf("%lld\n", ans);
    }
    return 0;
}