题目

题目描述： 
今天，HH成为一名设计师，他面临一个问题，因此他要求您提供帮助。
Treeisland是一个拥有n个城市和n-1条双向道路的国家，您可以从任何城市前往任何其他城市。
设计人员将设计一个计划，将n个城市分为n / 2对，以使n / 2对城市之间的长度之和最小。
现在，HH已完成它，但他不知道这是否正确，因此他想和您一起计算。
保证n为偶数。

输入描述：
 第一行包含一个正整数T（1≤T≤100），表示有T个测试用例。 
对于每个测试的情况：第一行包含一个正整数n（1≤n≤10 4），代表城市在Treeisland数，它的保证n是偶数。 
然后跟随n-1行。每行有三个正整数U，V和Len，（U≠V，1≤u≤n，1≤v≤n，1≤len≤109 指示存在u和v之间len个长度的道路）。 
 这保证您可以从任何城市到达任何城市。

输出描述：
对于每个测试用例，一行输出一个整数，代表最小长度之和。

解析

这道题没有复杂的算法，只是单纯的dfs，但是需要思考。
  • 我们先来简单描述一下这道题：我们每两个点组成一组，取得他们之间的长度。最后求最短长度总和。

算法讲解：
  1. 刚看到的时候，我觉得无从下手，因为又是一道求啥最短长度和的题目，吓到我人都懵掉了。看到邓老师讲解后豁然开朗。
  2. 我们要取得最短长度的话，我们就要尽量不重复选边（重复会造成资源浪费）。

    就像这个，你不选左边的，硬是要选右边的岂不是有点毛病。
  3. 所以在不重复选边的思考下，我们发现，每条边只有两种可能：选或不选！那么我们只要知道某条边什么时候选就行了。
    由这点我们就发现，我们不管怎么选边都没事，最后的边和一定的。
  4. 那么我们对着某一个节点来考虑这个问题：某一个节点的选择一般都是最近的节点（父节点），或者在已占用的情况下找一个远一点的（兄弟节点）。
  5. 但是为什么是父节点和兄弟节点呢？让我们来看下面这张图：

  6. 在这张图里面我们可以发现：左边三个节点无法内部消化，兄弟可以配在一起（父节点可以找前面的）。而四个节点的可以直接成双内部消化了。
  7. 所以我们得到的结论就是：当子树为奇数的时候，根节点一定会和前面的点相连（对叶节点同样适用，叶节点是奇数树，而且一定连边）。

操作方法：
  1. 知道算法后，操作就是其次比较难的地方了。在这个dfs里面我们要先明确我们的工作是什么。
  2. <1>我们要知道以某一点为根节点的子树大小（用于判断是否可内部消化）。<2>我们要得到我们的最小权和。
  3. 首先计算子树大小，我们在这里运用分治递归的思路，从小到大进行合并：我们用一个变量（cnt）累加根节点的每一条支路的节点数。
  4. 然后就是得到最小权和：我们可以在递归的时候添加一个变量用于保存当前路径（当前根节点和其父节点）的权值，是奇数就加上就好了（原因见算法讲解）。

打代码咯：
  1. 首先是老操作，前向星保存树形结构。
  2. 然后就可以进行我们惊险刺激的dfs了，这里唯一要注意的就是我们没有确定的根，随便选一个就好了（权值为啥都一样，反正总数是偶数也不用在意，我们还是填0）。
  3. 看代码吧~

AC代码 

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
//代码预处理区

const int MAX = 1e5 + 7;
int head[MAX], tot;
struct Node {
    int v, w, next;
} edge[MAX << 1];
ll ans;
//全局变量区

template<class T>inline void read(T& res);
void add_edge(int u, int v, int w);
int dfs(int u, int fa, int w);
//函数预定义区

int main() {
    int T; read(T);
    while (T--) {
        int n; read(n);
        tot = 0; memset(head, 0, sizeof head);
        for (int i = 1; i <= n - 1; i++) {
            int u, v, w; read(u); read(v); read(w);
            add_edge(u, v, w);
            add_edge(v, u, w);
        }
        ans = 0;
        dfs(1, 0, 0);
        printf("%lld\n", ans);
    }
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
void add_edge(int u, int v, int w) {
    tot++;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot;
}
int dfs(int u, int fa, int w) {
    int cnt = 1;//初始化为1表示计算自己这个点
    for (int i = head[u]; i; i = edge[i].next)
        if (edge[i].v != fa)
            cnt += dfs(edge[i].v, u, edge[i].w);
    //计算子树的总节点数
    if (cnt & 1) ans += w;
    //当前树节点为奇数则要加上与父节点的连接
    return cnt;
}
//函数区