POJ 2486 Apple Tree（树型DP）

题意：给你一棵树，树上的每个节点都有权值，从一个节点到另一个节点需要的步数是1，问从节点1开始，给你步数为K，问能得到的最大权值是多少。

定义dp[i][j][0]表示从节点i出发能走j步最后不回到i点能得到的最大权值是多少。

定义dp[i][j][1]表示从节点i出发能走j步最后回到i点能得到的最大权值是多少。

那么状态转移方法就可以知道了，如果还要回到u点，从节点u转移到节点v就需要两步，否则，就只需要一步，这是状态转移方程里面加一和加二的原因。

dp[u][i+2][0]=max(dp[u][i+2][0],dp[u][i-j][0]+dp[v][j][0]);
dp[u][i+2][1]=max(dp[u][i+2][1],dp[u][i-j][1]+dp[v][j][0]);
dp[u][i+1][1]=max(dp[u][i+1][1],dp[u][i-j][0]+dp[v][j][1]);

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=105;
struct Edge
{
	int v;
	Edge* nxt;
}memo[N*N],*cur,*adj[N];

int dp[N][N*2][2],n,K;

void dfs(int u,int fa)
{
	for(Edge* it=adj[u];it;it=it->nxt)
	{
		int v=it->v;
		if(v==fa) continue;
		dfs(v,u);
		for(int i=K;i>=0;i--)
		{
			for(int j=0;j<=i;j++)
			{
				dp[u][i+2][0]=max(dp[u][i+2][0],dp[u][i-j][0]+dp[v][j][0]);
				dp[u][i+2][1]=max(dp[u][i+2][1],dp[u][i-j][1]+dp[v][j][0]);
				dp[u][i+1][1]=max(dp[u][i+1][1],dp[u][i-j][0]+dp[v][j][1]);
			}
		}
	}
}
void addEdge(int u,int v)
{
	cur->v=v;
	cur->nxt=adj[u];
	adj[u]=cur++;
}
void init()
{
	cur=memo;
	memset(adj,0,sizeof(adj));
	memset(dp,0,sizeof(dp));
}
int main()
{
	while(scanf("%d%d",&n,&K)!=EOF)
	{
		init();

		for(int i=1;i<=n;i++)
		{
			scanf("%d",&dp[i][0][1]);
			dp[i][0][0]=dp[i][0][1];
		}
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			addEdge(u,v);
			addEdge(v,u);
		}

		dfs(1,-1);

		int res=0;
		for(int i=0;i<=K;i++) res=max(res,dp[1][i][1]);
		printf("%d\n",res);
	}
	return 0;
}