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\n",ans);

	}

	return 0;

}

巴特西

HDU 4313 Contest 2

最新文章

热门文章