题解:
http://www.cppblog.com/rakerichard/articles/105004.html
惊了,讨论子树大小能否dp真鸡儿麻烦,按照上面那份题解,可以不用分这么多类,可以直接用dp(U,K)表示能最多选K个,而非恰好选K个时的答案。
UPDATE:我真鸡儿傻逼,将不存在的结点记作0,根节点记作n+1,可以有效避免讨论结点的存在性。dp(0,K)=0。
#include<cstdio> #include<algorithm> #include<cstring> 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<K;++j){ if(siz[T[U].lc]>=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; }