poj2486 Apple Tree （树形dp+分组背包）

题目链接：https://vjudge.net/problem/POJ-2486

题意：一棵点权树，起点在1，求最多经过m条边的最大点权和。

思路：

　　树形dp经典题。用3维状态，dp[u][j][0/1]表示在子树u中走j步的最大价值（回到u/不回到u）。显然dp[u][j][1]>=dp[u][j][0]，所以dp[1][m][1]就是最终答案。

　　假设v为u的子结点，k为到v且在v中所用步数，那么转移方程分3步，为：

　　　　dp[u][j][0]=max(dp[u][j][0] , dp[u][j-k][0]+dp[v][k-2][0]) (k>=2)

　　　　dp[u][j][1]=max(dp[u][j][1] , dp[u][j-k][0]+dp[v][k-1][1]) (k>=1)

　　　　dp[u][j][1]=max(dp[u][j][1] , dp[u][j-k][1]+dp[v][k-2][0]) (k>=2)  （第3步容易忘掉）

AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=105;
const int maxm=205;
int n,m,cnt,a[maxn],head[maxn],dp[maxn][maxm][2];
struct node{
int v,nex;
}edge[maxn<<1];
void adde(int u,int v){
edge[++cnt].v=v;
edge[cnt].nex=head[u];
head[u]=cnt;
}
void dfs(int u,int fa){
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].v;
if(v==fa) continue;
dfs(v,u);
for(int j=m;j>=1;--j)
for(int k=1;k<=j;++k){
if(k>=2) dp[u][j][0]=max(dp[u][j][0],dp[u][j-k][0]+dp[v][k-2][0]);
if(k>=1) dp[u][j][1]=max(dp[u][j][1],dp[u][j-k][0]+dp[v][k-1][1]);
if(k>=2) dp[u][j][1]=max(dp[u][j][1],dp[u][j-k][1]+dp[v][k-2][0]);
}
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
cnt=0;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
head[i]=0;
for(int j=0;j<=m;++j)
dp[i][j][0]=dp[i][j][1]=a[i];
}
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
dfs(1,0);
printf("%dn",dp[1][m][1]);
}
return 0;
}