记录编号	268790	评测结果	AAAAA
题目名称	[HZOI 2016] 搜城探宝	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-06-12 19:16:32	内存使用	0.00 MiB

#include<cstdio>//scanf(),printf()
#include<cstring>//memset()
#include<algorithm>//max()
#include<queue>//队列
using namespace std;
const int maxn=30;
struct edge{
	int to;
	edge* prev;//previous的简写,以from(此处没有显式记录)为起点的上一条边
	edge():to(0),prev(NULL){}
}ee[maxn];
struct node{
	int data,lch,rch,prt;//data:节点的宝藏价值
	node(int data=0,int lch=0,int rch=0,int prt=0):
		data(data),lch(lch),rch(rch),prt(prt){}
	//令空儿子为0并不会引起误会,因为任何节点的子节点都不可能是根节点
}a[maxn];
void insert(int,int);
int dfs(int,int);
void bfs(int);
edge* last[maxn]={NULL};//指向以某个点为起点的最后一条边
int len=0;
int f[maxn][maxn];//f(i,j)表示树i使用j个钥匙(包括开i的门的那个)能获得的最大价值
bool vis[maxn][maxn]={{false}},vist[maxn]={false};
//前一个vis用于记忆化搜索,后一个vist用于广搜建树
int n,m,ans=0;
inline int MAIN(){
	freopen("hzoi_key.in","r",stdin);
	freopen("hzoi_key.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(m>n)m=n;//这是显然的,原因前面已经讲过了
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		insert(x,y);
	}
	bfs(1);//以1为根建树
	a[0].lch=1;
	for(int i=1;i<=n;i++)scanf("%d",&a[i].data);
	m+=2;//这里的原因前面也讲过了
	for(int i=2;i<=n;i++){
		memset(f,0,sizeof(f));
		memset(vis,0,sizeof(vis));
		//这两句话很重要,因为每次计算dp值时树已经发生了变化
		if(i==a[a[i].prt].lch){
			a[a[i].prt].lch=0;
			a[0].rch=i;
			ans=max(ans,dfs(0,m));
			a[a[i].prt].lch=i;
			a[0].rch=0;
		}
		else{
			a[a[i].prt].rch=0;
			a[0].rch=i;
			ans=max(ans,dfs(0,m));
			a[a[i].prt].rch=i;
			a[0].rch=0;
		}
		//以上为分情况处理,其实中间的求dp可以合并,但为了方便还原这里分开写
	}
	printf("%d",ans);
	return 0;
}
inline void insert(int x,int y){//添加一条从x到y的新边
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
inline int dfs(int i,int j){//计算dp值,需要使用记忆化搜索
	if(!j)return 0;
	if(vis[i][j])return f[i][j];//已经算过,直接返回答案
	vis[i][j]=true;//标记为"已经算过"
	if(a[i].lch&&a[i].rch)for(int k=0;k<j;k++)
		f[i][j]=max(f[i][j],dfs(a[i].lch,k)+dfs(a[i].rch,j-k-1));
	else if(a[i].lch)f[i][j]=dfs(a[i].lch,j-1);
	else if(a[i].rch)f[i][j]=dfs(a[i].rch,j-1);
	//这里省略了两个儿子都没有的情况,
	//因为如果没有儿子那么上面的三条if语句都不会满足
	return f[i][j]+=a[i].data;//这里利用了C++语言"赋值语句有返回值"的规定
}
inline void bfs(int st){//使用广度优先搜索建树,虽然数据太弱似乎并不需要搜索建树
	queue<int>q;
	q.push(st);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vist[x]=true;//标记x为"已完成建树操作"
		for(edge* e=last[x];e;e=e->prev){
			int y=e->to;
			if(vist[y])continue;
			//如果已经完成了y的建树操作则跳过,否则可能会把x的父亲误认为x的儿子
			if(!a[x].lch)a[x].lch=y;
			else a[x].rch=y;
			a[y].prt=x;
			q.push(y);//扩展节点
		}
	}
}
int haha=MAIN();
int main(){;}