http://acm.hust.edu.cn/vjudge/problem/18068
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 500+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m; int head[MAXN],vis[MAXN],ptr=1; int dp[MAXN][MAXN],num[MAXN],val[MAXN]; struct node{int y,next,val;}tree[MAXN<<2]; void init() { mem(head,-1); mem(vis,0); mem(dp,0); ptr = 1; } void add(int son,int fa) { tree[ptr].y=son; tree[ptr].next=head[fa]; head[fa]=ptr++; } void dfs(int rt) { num[rt] = vis[rt] = 1; dp[rt][1] = val[rt]; for(int i = head[rt];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(y); num[rt]+=num[y]; for(int j = num[rt];j>1;j--) { for(int k = 1;k<j;k++) { dp[rt][j] = max(dp[rt][j],dp[rt][j-k]+dp[y][k]); } } //pf("rt%d y%d ",rt,y); //for(int j = 1;j<=num[rt];j++) pf("%d ",dp[rt][j]); //blank; } } int main() { int i,j,k=1; while(~sf("%d%d",&n,&m) && m+n) { init(); for(i=1;i<=n;i++) { int x,y; sf("%d%d",&x,&y); add(x,i); add(i,x); val[i] = y; } dfs(0); pf("%d ",dp[0][m+1]); } }