https://www.lydsy.com/JudgeOnline/problem.php?id=2427
https://www.luogu.org/problemnew/show/P2515
dp简单题，然而因为数组开小了debug了两天？？？
（不过同时让我de出了一些题解的bug）
如果从属关系为环的话，显然其中一个选则全环都得选，于是tarjan缩点，变成了森林。
建虚点连接每个森林，剩余的就是树上背包了，与HDU1561：The more, The Better相同，但是因为n很小所以选择了O(n^2*m)的做法。
同时与那道题不同的是，因为体积可以为0，所以可能会出现有后效性的情况，特判之。
#include<map>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=;
const int M=;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int to,nxt;
}e[N*];
stack<int>q;
bool inq[N];
int pre[N],d[N][N];
int cnt,head[N],n,m,dp[N][M];
int val[N],w[N],weight[N],b[N];
int dfn[N],low[N],to[N],indeg[N],t,l;
inline void add(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
void dfs(int u){
for(int i=b[u];i<=m;i++)dp[u][i]=w[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dfs(v);
for(int j=m;j>=b[u];j--){
int tmp=dp[u][j];
for(int k=b[u];k<=j-b[v];k++){
if(k!=j)dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]);
else dp[u][j]=max(dp[u][j],tmp+dp[v][j-k]);
}
}
}
}
void tarjan(int u){
int v;
dfn[u]=low[u]=++t;
q.push(u);inq[u]=;
for(int i=head[u];i;i=e[i].nxt){
v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(inq[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
l++;
do{
v=q.top();q.pop();
inq[v]=;to[v]=l;
w[l]+=val[v];b[l]+=weight[v];
}while(v!=u);
}
}
int main(){
n=read(),m=read();
for(int i=;i<=n;i++)weight[i]=read();
for(int i=;i<=n;i++)val[i]=read();
for(int v=;v<=n;v++){
pre[v]=read();
if(pre[v])add(pre[v],v);
}
for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i);
memset(head,,sizeof(head));cnt=;
for(int i=;i<=n;i++){
int u=to[pre[i]],v=to[i];
if(!pre[i]||u==v)continue;
if(!d[u][v]){
d[u][v]=;add(u,v);indeg[v]++;
}
}
int rt=l+;
for(int i=;i<=l;i++)
if(!indeg[i])add(rt,i);
dfs(rt);
printf("%d\n",dp[rt][m]);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++