这题其实是一道树形背包+强连通分量缩点的图，我没怎么接触过强连通分量，所以第一时间下意识以为这题的结构是一棵树。实际上题目没有说明是树所以这个结构中可能包含有环，那么就需要使用缩点来构建这棵树了。
唯一的问题是我不会tarjan...
好经过两天的磨磨蹭蹭，我已经学会tarjan了，接下来来看看这道题的思路。在使用tarjan识别完图中的强连通分量（scc）以后，我们通常会将这些分量“染色”，染色就是将同一联通分量的结点赋一个相同的值，并保存在额外的数组里。但是首先要说清楚的是，这道题的题目描述中，有这样一句：
幸运的是，一个软件最多依赖另一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
很显然这样一个描述，其实是在说明这个图的结构可能包含环或者森林。且森林或者树中不会包含环，环是单独存在的。
于是，当我们将这个图中所有的scc进行染色以后，就可以利用在tarjan过程中保存的染色数组，以及之前在建树时可以保存的每个结点的父节点，来构建新树了，之后就是很常见的树状背包DP一下。
来写写看代码把：
code
#include<bits/stdc++.h>
using namespace std;
const int WN = 110;
int wi[WN],vi[WN],di[WN];
int cost[WN],value[WN],ischild[WN];
int he[WN],ne[WN],e[WN];
int cnt = 0;
int record[WN];
int dp[WN][WN*5];
int n,c;
int siz[WN];
int color[WN];int tot = 0;
int stack1[WN];int top = 0;
int low[WN],dfn[WN];
int index1 = 0;
int vis[WN];
void add(int a, int b){
e[cnt] =b;
ne[cnt] = he[a];
he[a] = cnt++;
}
void tarjan(int u){
stack1[++top] = u;
vis[u] = 1;
low[u] = dfn[u] = ++index1;
for(int i = he[u] ; i != -1 ; i = ne[i]){
int x = e[i];
if(dfn[x] == 0){
tarjan(x);
low[u] = min(low[u],low[x]);
}else if(vis[x] == 1){
low[u] = min(low[u],dfn[x]);
}
}
if(low[u] == dfn[u]){
tot++;
vis[u] = 0;
while(stack1[top+1]!=u){
color[stack1[top]] = tot;
vis[stack1[top--]] = 0;
}
}
}
//void dfs(int u)
//{
// for(int i=cost[u];i<=c;i++)dp[u][i]=value[u];
// for(int i=he[u];i!=-1;i=ne[i])
// {
// int v=e[i];
// dfs(v);
// for(int j=c-cost[u];j>=0;j--)
// {
// for(int q=0;q<=j;q++)
// {
// dp[u][j+cost[u]]=max(dp[u][j+cost[u]],dp[u][j+cost[u]-q]+dp[v][q]);
// }
// }
// }
//}
//void dfs(int u){
// for(int i = cost[u] ; i <= c ; i ++){
// dp[u][i] +=value[i];
// }
// for(int i = he[u]; i!=-1 ; i = ne[i]){
// int x = e[i];
// dfs(x);
// for(int j = c ; j >= 0 ; j --){
// for(int k = 0 ; k <= j-cost[u];k++){
// if(j>=k)dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[x][k]);
// }
// }
// }
//}
//使用上下界优化
void dfs(int u){
siz[u] =cost[u];
for(int j = c ; j >=cost[u] ; j --){
dp[u][j]+=value[u];
}
for(int i = he[u] ; i!=-1 ; i = ne[i]){
int x = e[i];
dfs(x);
for(int j = min(c,siz[u]+siz[x]); j >= 0 ; j --){
for(int k = max(0,j-siz[u]) ; k<=siz[x]&&k <= j-cost[u]; k++){
dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[x][k]);
}
}
siz[u]+= siz[x];
}
}
int main(void){
cin>>n>>c;
memset(he,-1,sizeof(he));
for(int i = 1 ; i <= n ; i ++){
cin>>wi[i];
}
for(int i = 1 ; i <= n ; i ++){
cin>>vi[i];
}
//初始化图
for(int i = 1 ; i <= n ; i ++){
cin>>di[i];
if(di[i]!=0)
add(di[i],i);
}
//找出所有scc
for(int i = 1 ; i <= n ; i ++){
if(dfn[i]==0)tarjan(i);
}
// cout<<tot<<endl;
memset(he,-1,sizeof(he));memset(ne,0,sizeof(ne));memset(e,0,sizeof(e));
cnt = 0;
//缩点建图,将color中的每个scc分量作为一个物品来进行建图
for(int i = 1 ; i <= n ; i ++){
cost[color[i]]+=wi[i];value[color[i]]+=vi[i];
if(color[i]!=color[di[i]]&&di[i]!=0){
// cout<<cost[color[i]]<<" "<<value[color[i]]<<endl;
add(color[di[i]],color[i]);
ischild[color[i]]++;
}
}
//将所有强连通分量设置一个虚拟根0,注意这里的scc可能存在之前的环，导致有三个结点是相同的值，需要记录并保存为一个物品
for(int i = 1 ; i <= tot ; i ++){
if(ischild[color[i]]==0&&record[color[i]] == 0){
add(0,color[i]);
record[color[i]] = 1;
}
}
dfs(0);
cout<<dp[0][c];
return 0;
}这题有一个需要注意的地方，用tarjan求出图中所有强连通分量以后，在建图时循环所有点，并将所有当前结点颜色等于父节点颜色的值跟一个虚拟结点连接。这时候需要注意，如果原来图中存在环会导致环中所有的点都将代表这个强连通分量跟虚拟节点生成一个连接，这时候需要记录跟虚拟节点连接的点是否已经连接过，才能生成一颗没有重复物品的树。
之后用树形背包来DP的时候用了一下上下界优化，确实快了不少。
image
