Question surface: Valley portal

Algorithm elements: tarjan + tree dp

Topic analysis:

1, General summary

It can be found that the points in a ring must be selected at the same time, so it is easy to think of tarjan shrinking points.
After shrinking, a DAG is formed. Due to the condition of the subject, d[i]=0 means that one software does not have another software as the premise, so there is a super source point 0. You can consider running through the tree dp (backpack on the tree) from 0 o'clock to get the answer.

II (detail 1): why can't topology dp be used to solve:

If you run the topology dp once, you can get the maximum weight chain with each point as the end point, but there is obviously a possibility of coincidence in each chain, so you can't directly synthesize the maximum weight chain with each point as the end point into the optimal solution of the whole DAG by running 01 knapsack again.
So topology dp obviously doesn't work.

This problem also tells us that the reduction point does not have to be solved by topological dp.

III (detail 2): how to forcibly select the current point in the tree dp

We use dp formula: f[u][j] to represent the maximum total value of the software that can be obtained by consuming j's storage space in the subtree with u root.
But don't forget that only when you select the root node can you select the points in the subtree.
Therefore, we add a restriction: for f[u][j], it is mandatory to select point U.

This is actually a kind of problem: how to forcibly select the root node of a subtree in the tree dp

The process of enumerating j and subtree cost k must be considered (modifying the transfer formula)
Without this condition, we would obviously write the state transition like this

order u A child node of is v
for(int j=sumw[u];j<=m;++j) f[u][j]=sumv[u]; 
for(int j=m;j>=0;--j)
{
	for(int k=0;k<=j;++k)
		f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}

Adding this restriction is equivalent to leaving enough storage space for selecting the root node

for(int j=sumw[u];j<=m;++j) f[u][j]=sumv[u]; 
for(int j=m-sumw[u];j>=0;--j)
{
	for(int k=0;k<=j;++k)
		f[u][j+sumw[u]]=max(f[u][j+sumw[u]],f[u][j+sumw[u]-k]+f[v][k]);
}

Because each location must leave enough space for u, and sumw[u] is added to each calculation space. In addition, the initial initialization is to assign sumv[u] to each unselected space, so sumv[u] must be selected.

Or there is another way to write it:
That is, the space selected in the part of the subtree that does not include u must be one sumw[u] less than the space selected in the part of the subtree that includes u, that is, u must be selected.

void dp(int now)
{
	for(int i=sumw[now];i<=m;++i) f[now][i]=sumv[now];
	for(int i=head2[now];~i;i=e2[i].nxt)
	{
		int v=e2[i].v;
		dp(v);
		for(int j=m;j>=sumw[now];--j)
		{
			for(int k=0;k<=j-sumw[now];++k)
			{
				f[now][j]=max(f[now][j],f[now][j-k]+f[v][k]);
			}
		}
	}
}

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=550;
int n,m,w[maxn],v[maxn],d[maxn],tot,col[maxn];
int dfn[maxn],low[maxn],Time,sumw[maxn],sumv[maxn];
int ecnt=-1,ecnt2=-1,head[maxn],head2[maxn];
int s[maxn],top,indu[maxn],f[105][505];
struct mint
{
	int nxt,u,v;	
}e[maxn],e2[maxn];
inline void addline(int u,int v)
{
	e[++ecnt].nxt=head[u];
	e[ecnt].u=u;
	e[ecnt].v=v;
	head[u]=ecnt;
}
inline void addline2(int u,int v)
{
	e2[++ecnt2].nxt=head2[u];
	e2[ecnt2].u=u;
	e2[ecnt2].v=v;
	head2[u]=ecnt2;	
}
void tarjan(int now)
{
	dfn[now]=low[now]=++Time;
	s[++top]=now;
	for(int i=head[now];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(!dfn[v])
		{
			tarjan(v);
			low[now]=min(low[now],low[v]);	
		}
		else if(!col[v]) low[now]=min(low[now],dfn[v]);
	}
	if(dfn[now]==low[now])
	{
		tot++;
		int cur;
		do
		{
			cur=s[top--];
			col[cur]=tot;
			sumw[tot]+=w[cur];
			sumv[tot]+=v[cur];
		}
		while(cur!=now);
	}
}
void dp(int now)
{
	for(int i=sumw[now];i<=m;++i) f[now][i]=sumv[now];
	for(int i=head2[now];~i;i=e2[i].nxt)
	{
		int v=e2[i].v;
		dp(v);
		for(int j=m-sumw[now];j>=0;--j)
		{
			for(int k=0;k<=j;++k)
			{
				f[now][j+sumw[now]]=max(f[now][j+sumw[now]],f[now][j+sumw[now]-k]+f[v][k]);
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	memset(head2,-1,sizeof(head2));
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	for(int i=1;i<=n;++i) scanf("%d",&v[i]);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&d[i]);
		addline(d[i],i);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
	for(int i=0;i<m;++i)
	{
		if(col[e[i].v] != col[e[i].u])
		{
			addline2(col[e[i].u],col[e[i].v]); 
			indu[col[e[i].v]]++;
		}
	}
	for(int i=1;i<=tot;++i) if(!indu[i]) addline2(0,i);
	dp(0);
	printf("%d",f[0][m]);
	return 0;	
}