CVBB ACM Team

POJ 2486

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define INF 0x3f3f3f3f
using namespace std;
int res,n,k,f[105][205][2],head[105],cnt,w[105],pa[105];
struct Node{int nxt,to;}Edges[105*2];
void addedge(int u,int v)
{
	Edges[++cnt].nxt=head[u];
	head[u]=cnt,Edges[cnt].to=v;
}
void dfs(int u)
{
	f[u][0][0]=f[u][0][1]=w[u];
	for(int i=head[u];~i;i=Edges[i].nxt)
	{
		int v=Edges[i].to;
		if(pa[u]==v)continue;
		pa[v]=u,dfs(v);
		for(int j=k;j;j--)
		{
			for(int l=0;l<=j;l++)
			{
				if(j-l-2>=0)f[u][j][0]=max(f[u][j][0],f[u][l][0]+f[v][j-l-2][0]);
				if(j-l-1>=0)f[u][j][1]=max(f[u][j][1],f[u][l][0]+f[v][j-l-1][1]);
				if(j-l-2>=0)f[u][j][1]=max(f[u][j][1],f[u][l][1]+f[v][j-l-2][0]);
				if(u==1)res=max(res,max(f[u][j][0],f[u][j][1]));
			}
		}
	}
}
int main()
{
	while(~scanf("%d%d",&n,&k))
	{
		cnt=0;
		memset(head,-1,sizeof(head));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)scanf("%d",&w[i]);
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			addedge(u,v),addedge(v,u);
		}
		res=w[1],dfs(1);
		printf("%d\n",res);
	}
	return 0;
}