没什么好说的。
非常简单的树dp
10分算法
其实是你dp打错了才会10分。
1个注意点（由于博主沙雕打法导致的）
if(x!=0) { for(ll j=m;j>=w1[x];j--) f[x][j]=f[x][j-w1[x]]+v1[x]; for(ll j=w1[x]-1;j;j--) f[x][j]=0; }
没清零！（上面给它赋值了但实施上它本来就不该有值）
40分算法
没打tarjan就会40分。
事实上当你发现你一直40wrong ans并且改不出来时就应该想想tarjan
100分
如果打了tarjan就100分了。
和某个叫「选课」的题特别像。
选课会打这个就会。
以下是本人丑陋的代码。
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define A 2100 4 using namespace std; 5 ll ver[A],f[A][A],fa[A],dis[A],deep[A],chatot=0,root,sum[A],w[A],d[A],v[A],num=0,top=0,ins[A],sta[A],dfn[A],low[A],cnt=0,scc[110][110],belong[A]; 6 ll head2[A],head[A],nxt[A],nxt2[A],ver2[A],tot2=0,tot=0,du[A],v1[A],w1[A]; 7 bool flag[A],vis[A]; 8 ll n,m,k,t,xx,yy,zz; 9 inline ll read(){ll f=1,x=0;char ch=getchar();while(!isdigit(ch)){if(ch==‘-‘) f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;} 10 inline void add(ll x,ll y){fa[y]=x,ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;} 11 inline void add2(ll x,ll y){ver2[++tot2]=y,nxt2[tot2]=head2[x],head2[x]=tot2;} 12 inline void rebuilt() 13 { 14 for(ll i=1;i<=n;i++) 15 { 16 for(ll j=head[i];j;j=nxt[j]) 17 { 18 ll y=ver[j]; 19 if(belong[y]!=belong[i]) 20 add2(belong[i],belong[y]),du[belong[y]]++; 21 } 22 } 23 } 24 inline ll tarjan(ll x) 25 { 26 dfn[x]=low[x]=++num; 27 sta[++top]=x;ins[x]=1; 28 for(ll i=head[x];i;i=nxt[i]) 29 { 30 ll y=ver[i]; 31 if(dfn[y]==0) 32 { 33 tarjan(y); 34 low[x]=min(low[x],low[y]); 35 } 36 else if(ins[y]) 37 low[x]=min(low[x],dfn[y]); 38 } 39 if(dfn[x]==low[x]) 40 { 41 ++cnt; 42 ll yy=0; 43 while(1) 44 { 45 yy=sta[top--]; 46 ins[yy]=0; 47 belong[yy]=cnt; 48 v1[cnt]+=v[yy]; 49 w1[cnt]+=w[yy]; 50 if(yy==x) 51 break; 52 53 } 54 } 55 } 56 void dfs(ll x) 57 { 58 f[x][0]=0; 59 for(ll i=head2[x];i;i=nxt2[i]) 60 { 61 ll y=ver2[i]; 62 dfs(y); 63 for(ll j=m;j>=0;j--) 64 for(ll k=j;k>=0;k--) 65 f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]); 66 } 67 if(x!=0) 68 { 69 for(ll j=m;j>=w1[x];j--) 70 f[x][j]=f[x][j-w1[x]]+v1[x]; 71 for(ll j=w1[x]-1;j;j--) 72 f[x][j]=0; 73 } 74 } 75 int main() 76 { 77 n=read(),m=read(); 78 for(ll i=1;i<=n;i++) 79 w[i]=read(); 80 for(ll i=1;i<=n;i++) 81 v[i]=read(); 82 for(ll i=1;i<=n;i++) 83 { 84 d[i]=read(); 85 add(d[i],i); 86 } 87 for(ll i=1;i<=n;i++) 88 if(!dfn[i]) tarjan(i); 89 rebuilt(); 90 for(ll i=1;i<=cnt;i++) 91 { 92 if(!du[i]) 93 add2(0,i); 94 } 95 dfs(0); 96 cout<<f[0][m]<<endl; 97 }
原文：https://www.cnblogs.com/znsbc-13/p/11172866.html
