题目链接：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("%d\n",dp[1][m][1]); } return 0; }