发之前突然在前面加一句，大部分题解都很简单，其实没什么不好，点到点上就行了。只是对萌新来说有点痛苦，所以我写的都比较详细，希望可以帮助到萌新（想起了痛苦的往事），要是还可以的话点个赞呗。另如果发现错误烦请指正。

划重点：Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities.这句话说有个城市条双向道路，且从任意一个城市可以到达另一个城市，说明是一颗树。

问题：要把个点两两配对，使得路径之和最小，一定是偶数。

基本思路：每个点和就近的配对，问题是当就近的点不止一个时该怎么选择？如下图所示的树中点是选点还是选点亦或者更远的点呢？

树

结论： 如果某条边连接的子树中的结点个数是奇数则选择该边，是偶数则不选。

  • 奇数以子树e为例，如果不选w2边的话，那么e子树中两两配对必定会剩下一个，剩下的那一个去和其他点配对的话路径长度会不小于w2。
  • 偶数以子树a为例，如果选了w1边的话，同理a子树中无论怎么配对始终会剩下一个，而剩下的那一个去和其他点配对必定会经过点s，路径长度不小于w1。
  • 如果有多个奇数结点的子树，都要选吗？怎么理解？还是以子树a为例，a有b、c、d三个奇数结点的子树，所以w3、w4、w5三条边都要选。但选了不代表a就一定要和b配对，a可以配对c，然后b和d配对。选了只是说在子树a的最优解决方案中会有w3这条边。
  • 以此推到任意子树的解，选择某条边并不是说根结点一定和该边对应的结点配对，而是说在这颗子树的最优解中有这条边，而不关心具体的配对方案。

严谨：是结点而不是节点！！！敲了半天节点感觉怪怪的，幸好百度了一下。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 2e5 + 117;

int t, n;
int u, v;
LL w, sum;
bool vis[MAXN];
struct Edge {
    int v, ne;
    LL w;
} edge[MAXN];
int head[MAXN], tot;
void init() {
    sum = tot = 0;
    memset(vis, false, sizeof(vis));
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, LL w) {
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
int dfs(int id) {
    vis[id] = true;
    int ret = 1, num;
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        if(vis[edge[i].v]) continue;
        num = dfs(edge[i].v);
        if(num & 1) sum += edge[i].w;
        ret += num;
    }
    return ret;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        init();
        scanf("%d", &n);
        for(int i = 1; i < n; i++) {
            scanf("%d%d%lld", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        dfs(1);
        printf("%lld\n", sum);
    }
    return 0;
}