题解：

http://www.cppblog.com/rakerichard/articles/105004.html

惊了，讨论子树大小能否dp真鸡儿麻烦，按照上面那份题解，可以不用分这么多类，可以直接用dp(U,K)表示能最多选K个，而非恰好选K个时的答案。

UPDATE：我真鸡儿傻逼，将不存在的结点记作0，根节点记作n+1，可以有效避免讨论结点的存在性。dp(0,K)=0。

#include
     
      #include
      
       #include
       
        using namespace std;int f[310][310],siz[310];struct Node{	int lc,rc,v;}T[310];int n,m;int dp(int U,int K){	if(f[U][K]!=-1){		return f[U][K];	}	if(K==0){		return f[U][K]=0;	}	if(siz[U]==1 && K==1){		return f[U][K]=T[U].v;	}	if(T[U].rc){		if(siz[T[U].rc]>=K){			f[U][K]=dp(T[U].rc,K);		}		if(siz[T[U].rc]>=K-1){			f[U][K]=max(f[U][K],dp(T[U].rc,K-1)+T[U].v);		}	}	if(T[U].lc){		if(!T[U].rc){			f[U][K]=max(f[U][K],dp(T[U].lc,K-1)+T[U].v);		}		else{			for(int j=0;j
        
         =j && siz[T[U].rc]>=K-j-1){					f[U][K]=max(f[U][K],dp(T[U].lc,j)+dp(T[U].rc,K-j-1)+T[U].v);				}			}		}	}	return f[U][K];//	f[U][K]=max(f[right[i]][j],d[left[i]][k]+d[right[i]][j-k-1]);}void dfs(int U){	siz[U]=1;	if(T[U].lc){		dfs(T[U].lc);		siz[U]+=siz[T[U].lc];	}	if(T[U].rc){		dfs(T[U].rc);		siz[U]+=siz[T[U].rc];	}	}int main(){//	freopen("vijos1180.in","r",stdin);	memset(f,-1,sizeof(f));	int x;	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i){		scanf("%d%d",&x,&T[i].v);		if(!T[x].lc){			T[x].lc=i;		}		else{			int U=T[x].lc;			while(T[U].rc){				U=T[U].rc;			}			T[U].rc=i;		}	}	dfs(0);	printf("%d\n",dp(T[0].lc,m));	return 0;}