题解：软件安装

题目：

https://www.luogu.com.cn/problem/P2515

注意软件的依赖关系可能形成一个环，a依赖b，b依赖c，c依赖a，如果想要让环上的一个软件起作用必须得下载环上的所有软件。所以需要先缩点。

缩点完成后重新建图，该题就是经典的树形依赖背包问题。

定义dp[i][j]为以i为根的子树，在选择了i的前提下背包容量为j时的最大价值。
dp过程中，外层循环枚举背包容量，内层循环枚举分配给当前子树的背包容量，然后对于父节点u当前背包容量为j和子节点v以及分配给子树的背包容量为k，那么dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k])，父节点和遍历到v之前的其他子树用j-k容量的最大价值加上子树v用k容量产生的最大价值。因为要提前知道子节点的情况，所以进行递归，从下往上更新。

考虑到可能会有多棵树，所以创建一个虚拟节点0连接每棵树的根节点。那么dp完后的答案就是dp[0][m]

dp部分：

voiddfs(intu){if(cost[u]>m)//父节点的容量已经超过整个背包容量,直接放弃这棵子树return;dp[u][cost[u]]=val[u];//先选择父节点(这棵子树的根节点)for(intv:ad[u]){dfs(v);//递归收集子树的情况for(intj=m;j>=cost[u];j--)//倒着枚举背包容量,保证只选择该子树一次{for(inti=0;i<=j-cost[u];i++)//枚举可以分配给这棵子树的容量{dp[u][j]=max(dp[u][j],dp[u][j-i]+dp[v][i]);}}}}

软件多次安装价值不会叠加，所以是01背包问题。外层循环需要倒着枚举，因为dp[u][j]的更新需要依赖dp表同层且列数更小的dp[u][j-i]，需要保证dp[u]这一层j列前的数据是上一次产生的数据。如果正着遍历的话，dp[u][j-i]可能已经被j-i列前面以及子树v的数据更新过，这代表已经选择了子树v一次，如果用这个数据去更新dp[u][j]的话，会导致v又被选择一次。

可能出现的情况：

正着遍历是先1后2，j-i位置已经算入了子树v的价值，到位置j时，依赖j-i位置和子树v进行更新，v会再次被算入。总之正序遍历会导致v的贡献被累加多次，需要保证j前面的数据还没有被更新过，所以需要倒着进行更新。

总代码：

//缩点建图统计入边复杂度为O(n),去重为O(nlogn),每条树边进行一次dp,dp过程为O(n*m^2)//前两项过小忽略,整体复杂度为O(n*m^2)#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineinf1e18constintN=105;constintM=505;intc[N],v[N],in[N];//c:软件容量 v:软件价值 in:入度intdfn[N],low[N],stk[N];intscc[N],ins[N],cost[N],val[N];//scc:每个点所在的强连通分量编号//cost:强连通分量的容量 val:强连通分量的价值intdp[N][M];//dp[i][j] 以i为根的子树,选择i的前提下背包容量为j的最大价值vector<int>adj[N],ad[N];intn,m,ti,tp,id;voidtarjan(intu){dfn[u]=low[u]=++ti;stk[++tp]=u;ins[u]=1;for(intv:adj[u]){if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}elseif(ins[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){id++;do{intx=stk[tp];scc[x]=id;ins[x]=0;cost[id]+=c[x];val[id]+=v[x];}while(stk[tp--]!=u);}}voiddfs(intu){if(cost[u]>m)//父节点的容量已经超过整个背包容量,直接放弃这棵子树return;dp[u][cost[u]]=val[u];//先选择父节点(这棵子树的根节点)for(intv:ad[u]){dfs(v);//递归收集子树的情况for(intj=m;j>=cost[u];j--)//倒着枚举背包容量,保证只选择该子树一次{for(inti=0;i<=j-cost[u];i++)//枚举可以分配给这棵子树的容量{dp[u][j]=max(dp[u][j],dp[u][j-i]+dp[v][i]);}}}}voidsolve(){cin>>n>>m;for(inti=1;i<=n;i++)cin>>c[i];for(inti=1;i<=n;i++)cin>>v[i];for(inti=1;i<=n;i++){intx;cin>>x;if(x==0)continue;adj[x].push_back(i);}for(inti=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(intu=1;u<=n;u++){inta=scc[u];for(intv:adj[u]){intb=scc[v];if(a==b)continue;ad[a].push_back(b);in[b]++;}}for(inti=1;i<=id;i++){if(in[i]==0){ad[0].push_back(i);}}for(inti=1;i<=id;i++){sort(ad[i].begin(),ad[i].end());ad[i].erase(unique(ad[i].begin(),ad[i].end()),ad[i].end());}dfs(0);cout<<dp[0][m]<<endl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT=1;// cin >> T;while(T--){solve();}return0;}