http://acm.hdu.edu.cn/showproblem.php?pid=1561
很容易想到如果是要攻克v城需要先攻克u城的话，可以建u到v的边。但是如果能够直接攻克u城呢？无边可建，这样就无法形成一棵树。因此虚拟出一个0结点去连接可直接攻克的城。这样只需多打一次0城即可。定义状态dp[i][j]表示当前结点为i时，选取j个节点（j为i的子节点或i）能获得的最大价值。
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v[u][i]][k])表示：
在u号点的第i个子节点中选k个点加上在u号点选j-k个子节点与直接在u号点选j个子节点那个更优。
显然dp[i][1]=val[1]，剩下的就是01背包了，感觉还是不太熟。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=;
vector<int> v[maxn];
int dp[maxn][maxn];
int N,M,x;
int val[maxn]; void dfs(int u,int m)
{
dp[u][]=val[u];
int len=v[u].size();
for(int i=;i<len;i++){
if(m>) dfs(v[u][i],m-);
for(int j=m;j>;j--)//由于0节点必选，所以j>1就行了
for(int k=;k<j;k++)
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v[u][i]][k]);
}
} int main()
{
while(cin>>N>>M&&!(N==&&M==))
{
memset(dp,,sizeof(dp));
memset(val,,sizeof(val));
for(int i=;i<=N;i++) v[i].clear();
for(int i=;i<=N;i++){
cin>>x>>val[i];
v[x].push_back(i);
}
dfs(,M+);
cout<<dp[][M+]<<endl;
}
return ;
}