题号 NC13886
Shortest Path
西南交通大学第十三届ACM决赛
题意：
一棵偶数节点的树，分成n/2对，两两一组，所有组的路径之和最小是多少？
题解：
如果两个点之间相连将另外两个相连的点覆盖，那么完全可以改变相连方式

改变后路径更小，也就是说两两一组的点都不会覆盖其他点
那么每个点与其他点配对就有两者选择，一个与兄弟节点配对（中间跨过父亲点），另一个就是与父亲节点相连，这样选择肯定是最优的
如果这个节点所在的自树里有偶数个节点，那么他们内部配对就可以了（好像有什么怪怪的）
如果有奇数个节点，还有把父亲节点拉进来一起配对（这样才能组成偶数个）
来上代码：


#include<bits/stdc++.h>
using namespace std;
const int maxx=1e4+5;
typedef long long ll;
int head[maxx];
int cnt=0;
ll x,y,z;
ll ans;
struct node
{
   
	ll w,v,u,next;
}edge[maxx*2];
void addt(int u,int v,int w)
{
   
	edge[++cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
	
}
ll dfs(ll u,ll f,ll w)
{
   
	ll sum=1;
	for(int i=head[u];i;i=edge[i].next)
	{
   
		if(edge[i].v!=f)sum+=dfs(edge[i].v,u,edge[i].w);
	}
	if(sum%2)ans+=w;
	return sum;
}
int main()
{
   
	int T;
	int n;
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
   
		cin>>n;
		memset(head,0,sizeof(head));
		cnt=0;
		ans=0;
		
		for(int i=1;i<n;i++)
		{
   
			scanf("%lld%lld%lld",&x,&y,&z);
			addt(x,y,z);
			addt(y,x,z); 
		}
		dfs(1,0,0);
		printf("%d\n",ans);
		
	}
	return 0;
}
//树上dfs