记录编号	269173	评测结果	AAAAA
题目名称	[HZOI 2016] 搜城探宝	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-06-13 11:19:39	内存使用	0.35 MiB

#include<cstdio>
#include<cctype>
int read(){
	char ch;int x;bool minus=false;
	while(ch=getchar(),!isdigit(ch)&&ch!='-');
	if(ch=='-'){
		minus=true;
		ch=getchar();
	}
	x=ch-'0';
	while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
	return minus?-x:x;
}
const int maxn=25;
struct edge{
	int to,next;
}lst[maxn<<2];int len=1;
int first[maxn];
void addedge(int a,int b){
	lst[len].to=b;
	lst[len].next=first[a];
	first[a]=len++;
}
int w[maxn],p[maxn],lch[maxn],rch[maxn];
int f[maxn][maxn][maxn];
bool vis[maxn];
void dfs1(int rt){
	for(int pt=first[rt];pt;pt=lst[pt].next){
		if(lst[pt].to==p[rt])continue;
		p[lst[pt].to]=rt;
		if(lch[rt])rch[rt]=lst[pt].to;
		else lch[rt]=lst[pt].to;
		dfs1(lst[pt].to);
	}
}
int n,k;
int max(int a,int b){
	return a>b?a:b;
}
void dfs2(int x){
	if(vis[x])return;
	vis[x]=true;
	if(!lch[x]){//叶节点 
		for(int i=0;i<=n;++i){//不得进入i 
			if(i==x)continue;
			for(int j=1;j<=k;++j){//j把钥匙 
				f[x][i][j]=w[x];
			}
		}
	}else if(!rch[x]){//仅左子 
		dfs2(lch[x]);
		for(int i=0;i<=n;++i){//不得进入i 
			if(i==x)continue; 
			for(int j=1;j<=k;++j){//j把钥匙 
				f[x][i][j]=f[lch[x]][i][j-1]+w[x];
			}
		}
	}else{
		dfs2(lch[x]);dfs2(rch[x]);
		for(int i=0;i<=n;++i){
			if(i==x)continue;
			for(int j=1;j<=k;++j){
				for(int l=0;l<j;++l){//左子使用几把钥匙 
					f[x][i][j]=max(f[x][i][j],w[x]+f[lch[x]][i][l]+f[rch[x]][i][j-1-l]);
				}
			}
		}
	}
}
int main(){
	freopen("hzoi_key.in","r",stdin);
	freopen("hzoi_key.out","w",stdout);
	n=read();k=read()+1;
	int a,b;
	for(int i=1;i<n;++i){
		a=read();b=read();
		addedge(a,b);
		addedge(b,a);
	}
	for(int i=1;i<=n;++i)w[i]=read();
	dfs1(1);
	for(int i=1;i<=n;++i){
		if(!vis[i])dfs2(i);
	}
	int ans=0;
	for(int i=0;i<=n;++i)//传送到i 
		for(int s=0;s<=k;++s)//s:在起点处使用几个钥匙 
			ans=max(ans,f[1][i][s]+f[i][0][k-s]);
	printf("%d\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}