Problem

每个软件都要安装某些软件才能安装，而且都有体积和价值，求安装的价值最大值

Solution

对于每个环，我们可以知道必须全部一起取或者不取，因此我们先用Tarjan缩点

然后我们用一个树形DP就可以解决了

Notice

注意这颗树是如果一个节点没取，后面就都不能取了

Code

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define sqz main

#define ll long long

#define reg register int

#define rep(i, a, b) for (reg i = a; i <= b; i++)

#define per(i, a, b) for (reg i = a; i >= b; i--)

#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)

#define travel2(i, u) for (reg i = head2[u]; i; i = edge2[i].next)

const int INF = 1e9;

const double eps = 1e-6, phi = acos(-1);

ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}

ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}

void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}

int f[105][1005];

int Time = 0, num1 = 0, num2 = 0, scc = 0, n, m;

stack<int> Stack;

struct node

{

	int vet, next;

}edge[505], edge2[505];

int head[105], head2[105], dfn[105], low[105], in[105], belong[105], v[105], w[105], V[105], W[105], flag[105];

void addedge(int u, int v)

{

	edge[++num1].vet = v;

	edge[num1].next = head[u];

	head[u] = num1;

}

void add(int u, int v)

{

	in[v]++;

	edge2[++num2].vet = v;

	edge2[num2].next = head2[u];

	head2[u] = num2;

}

void Tarjan(int u)

{

	dfn[u] = low[u] = ++Time;

	Stack.push(u);

	flag[u] = 1;

	travel(i, u)

	{

		int v = edge[i].vet;

		if (!dfn[v])

		{

			Tarjan(v);

			low[u] = min(low[u], low[v]);

		}

		else if (flag[v]) low[u] = min(low[u], dfn[v]);

	}

	if (low[u] == dfn[u])

	{

		int t; scc++;

		do

		{

			t = Stack.top();

			Stack.pop();

			belong[t] = scc;

			flag[t] = 0;

			V[scc] += v[t];

			W[scc] += w[t];

		}while (t != u);

	}

}

void dp(int u)

{

	travel2(i, u)

	{

		int v = edge2[i].vet;

		dp(v);

		per(j, m - V[u], 0)

			rep(k, 0, j) f[u][j] = max(f[u][j], f[u][k] + f[v][j - k]);

	}

	per(j, m, V[u]) f[u][j] = f[u][j - V[u]] + W[u];

	per(j, V[u] - 1, 0) f[u][j] = 0;

}

int sqz()

{

	n = read(), m = read();

	rep(i, 1, n) v[i] = read();

	rep(i, 1, n) w[i] = read();

	rep(i, 1, n) addedge(read(), i);

	rep(i, 0, n)

		if (!dfn[i]) Tarjan(i);

	rep(u, 1, n)

		travel(i, u)

		{

			int v = edge[i].vet;

			if (belong[u] != belong[v]) add(belong[u], belong[v]);

		}

	rep(i, 1, scc) if (!in[i]) add(0, i);

	dp(0);

	printf("%d\n", f[0][m]);

	return 0;

}