POJ 2486 经典树形dp

Description

Input

Output

Sample Input

2 1 
0 11
1 2
3 2
0 1 2
1 2
1 3

Sample Output

11
2

题意：一个n个节点的树，每个节点都有一个权值，从1出发，走k步，所能得到的最大权值，每个节点的权值只能算一次。

经典树形dp，理解了好久，终于看懂了。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-4 14:10:17
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int head[110],tol,dp[110][310][2],weight[110],m;
struct node{
	int next,to;
}edge[300];
void add(int u,int v){
	edge[tol].to=v;
	edge[tol].next=head[u];
	head[u]=tol++;
}
void dfs(int u,int fa){
	for(int i=0;i<=m;i++)
		dp[u][i][0]=dp[u][i][1]=weight[u];
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,u);
		for(int j=m;j>=0;j--)
			for(int k=0;k<=j;k++){
				dp[u][j+2][0]=max(dp[u][j+2][0],dp[u][j-k][0]+dp[v][k][0]);//u返回，v返回
				dp[u][j+2][1]=max(dp[u][j+2][1],dp[u][j-k][1]+dp[v][k][0]);//从u出发到v，v返回经过u访问u的其他子树不返回。
				dp[u][j+1][1]=max(dp[u][j+1][1],dp[u][j-k][0]+dp[v][k][1]);//从u的其他子树返回u，再访问u的子树v并不返回。
			}
	}
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int i,j,k,n;
	 while(~scanf("%d%d",&n,&m)){
		 memset(head,-1,sizeof(head));tol=0;
		 memset(dp,0,sizeof(dp));
		 for(i=1;i<=n;i++)
			 scanf("%d",&weight[i]);
		 for(i=1;i<n;i++){
			 scanf("%d%d",&j,&k);
			 add(j,k);
			 add(k,j);
		 }
		 dfs(1,-1);
		 printf("%d\n",dp[1][m][1]);
	 }
     return 0;
}

POJ 2486 经典树形dp

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18923397