HDU 4313 Contest 2

很明显的树形DP了。但网上有的说可以用并查集。。。。

考虑一棵子树，当根结点有机器人时，则必定所有子树都要和根结点断开，而根结点向上返回的路径值则为其父结点与根结点连边的权值。

当根结点安全时，假设其子树有K个危险结点，而由于K个结点需要两两不能相连，那么，至少断开K-1个结点。则把权值最小的K-1断开即可。而剩下的那个结点与根结点的边权值则返上至上一层。这时，相当于K-1个结点都从树中剪去，变成了一条单路径的树了吧，则若要断开剩下的结点与其他点的通路（假设要与祖父结点断开），则必定是要断开剩下结点与祖父结点该路径上权值最小的边。于是，返回的便是最小权值的边。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100005
using namespace std;

struct Edge{
	int u,v;
	int cost,next;
}edge[N*2];
int head[N],tot;
__int64 ans;
bool mech[N];

void addedge(int u,int v,int c){
	edge[tot].u=u;
	edge[tot].v=v;
	edge[tot].cost=c;
	edge[tot].next=head[u];
	head[u]=tot++;
}

int dfs(int now,int parent,__int64 parval){
	__int64 maxi=0;__int64 sum=0,tmp;
	for(int e=head[now];e!=-1;e=edge[e].next){
		if(parent==edge[e].v) continue;
		tmp=dfs(edge[e].v,now,edge[e].cost);
		maxi=max(maxi,tmp);
		sum+=tmp;
	}
	if(!mech[now])
	ans+=(__int64)(sum-maxi);
	else ans+=(__int64)sum;
	if(mech[now])
	return parval;
	return min(parval,maxi);
}

int main(){
	int T,n,k,u,v,c;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		memset(head,-1,sizeof(int)*(n+1));
		memset(mech,false,sizeof(bool)*(n+1));
		tot=0;
		for(int i=1;i<n;i++){
			scanf("%d%d%d",&u,&v,&c);
			addedge(u,v,c);
			addedge(v,u,c);
		}
		for(int i=1;i<=k;i++){
			scanf("%d",&u);
			mech[u]=true;
		}
		ans=0;
		dfs(0,-1,0);
		printf("%I64d
",ans);
	}
	return 0;
}