https://www.luogu.org/PRoblem/show?pid=2014 我一开始想不出来，看了题解后却发现是最基本的模型 唉~ 这里因为是森林所以我们简单的把森林合并到一个节点0； f[i][j]表示再i点的子孙里取j个的解； 当然不包括i；
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define Ll long longusing namespace std;struct cs{ int to,next,vv;}a[3001];int head[3001],v[3001],f[3001][3001];int n,m,ll,x,y,z,nn;void init(int x,int y){ ll++; a[ll].to=y; a[ll].next=head[x]; head[x]=ll;}int dfs(int x){ f[x][0]=v[x]; if(head[x]==-1)return 1; int sum=0,son; for(int k=head[x];k!=-1;k=a[k].next){ son=dfs(a[k].to); sum+=son; for(int j=sum;j;j--) for(int i=0;i<=son;i++) if(j-i-1>=0)//这个-1，1代表a[k].to节点本身 f[x][j]=max(f[x][j],f[x][j-i-1]+f[a[k].to][i]); } return sum+1;//这个+1，加上想节点自己 }int main(){ memset(head,-1,sizeof head); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&x,&v[i]); init(x,i); } nn=dfs(0); printf("%d",f[0][m]);}新闻热点
疑难解答
