ZOJ 3201 Tree of Tree(樹形背包DP)

dp[i][j]表示在i結點上選擇j個結點能獲得的最大值,j的值最大自然是以i為根的子樹的結點數量.

dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k])//方程意義就是在i結點上選擇j個點的最優值等于 max(目前值,在i的一顆子樹上選擇j-k個結點+在i的子樹v上選擇k個點) (k=1 2 ... j-1).枚舉j和k.

j-1因為必須要把i算進去

#include <iostream>
#include <memory.h>
#include <cstdio>
using namespace std;
const int maxn=101;
struct edge{
	int v,next;
}es[maxn*2];
int head[maxn],dp[maxn][maxn],v[maxn],N,K;
void addEdge(int u,int v,int eidx){
	es[eidx].v=v;
	es[eidx].next=head[u];
	head[u]=eidx;
}
int dfs(int u,int fa){
	dp[u][1]=v[u];
	int tot=1;
	for (int ne=head[u];ne!=-1;ne=es[ne].next){
		int v=es[ne].v;
		if(v==fa)continue;
		tot+=dfs(v,u);
		for (int j=tot;j>=1;--j){
			for (int k=1;j-k>=1;++k){
				dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
			}
		}
	}
	return tot;
}
int main(){
	while (scanf("%d%d",&N,&K)==2){
		memset(dp,0,sizeof(dp));
		memset(head,-1,sizeof(head));
		for (int i=0;i<N;++i){
			scanf("%d",&v[i]);
		}
		int eidx=0;
		for (int i=0;i<N-1;++i){
			int u,v;
			scanf("%d%d",&u,&v);
			addEdge(u,v,eidx++),addEdge(v,u,eidx++);
		}
		dfs(0,-1);
		int ans=0;
		for (int i=0;i<N;++i){
			ans=max(ans,dp[i][K]);
		}
		printf("%d\n",ans);
	}
	return 0;
}