https://ac.nowcoder.com/acm/problem/13886

题意:

给一棵树，保证树的结点个数是偶数，定义点对的价值是他们的距离，求将这棵树分成 n/2 个点对之后，这些点对的最小价值。

解法：

贪心的考虑，我们希望使得一颗树内的点两两组合，这样代价会最小，如果这棵树的结点个数是偶数个的话，我们将他在树内的所有结点两两结合。否则，为了代价最小，我们选择子树的根节点向子树外连边，其他的偶数个结点连边，这样代价会最小。
所以答案就是所有奇数个数节点的子树的根节点到他爸爸的距离。就和树剖的dfs1一样，先求出子树的大小，然后判断是否是奇数即可一次dfs解决。 
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e4 + 5;
struct edge
{
	int to;
	ll w;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot;
void init()
{
	memset(head, -1, sizeof(head));
	tot = 1;
}
void add(int a, int b, ll c)
{
	e[tot] = edge{ b,c,head[a] };
	head[a] = tot++;
}
int sz[MAXN];
ll ans;
void dfs(int u, int f)
{
	sz[u] = 1;
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int to = e[i].to;
		if (to == f)
			continue;
		dfs(to, u);
		sz[u] += sz[to];
		if (sz[to] & 1)
			ans += e[i].w;
	}
}
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		ans = 0;
		init();
		int n;
		sc("%d", &n);
		for (int i = 1; i < n; i++)
		{
			int a, b; ll c;
			sc("%d%d%lld", &a, &b, &c);
			add(a, b, c);
			add(b, a, c);
		}
		dfs(1, 0);
		pr("%lld\n", ans);
	}
}