题目链接
看到代价和价值这两个关键词，肯定是首先要想到背包的。
但是图中并没有说这是棵树，所以先要(Tarjan)缩点，然后就是选课了，跑一遍树形背包就好了。
注意：缩点后应该是一个森林，应该用一个虚点连接所有根。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 110;
const int MAXM = 1010;
struct Edge{
int next, from, to;
}e[MAXM << 1];
int head[MAXN], num;
inline void Add(int from, int to){
e[++num] = (Edge){ head[from], from, to };
head[from] = num;
}
int vis[MAXN], stack[MAXN], dfn[MAXN], low[MAXN], sum[MAXN], w[MAXN], v[MAXN], W[MAXN], V[MAXN], fa[MAXN], belong[MAXN];
int s[MAXN], t[MAXN], f[MAXN][MAXM], in[MAXN];
int n, m, top, ID, cnt, ans;
void Tarjan(int u){
dfn[u] = low[u] = ++ID;
vis[u] = 1; stack[++top] = u;
for(int i = head[u]; i; i = e[i].next)
if(!dfn[e[i].to]){
Tarjan(e[i].to);
low[u] = min(low[u], low[e[i].to]);
}
else if(vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]);
if(dfn[u] == low[u]){
++cnt;
do{
W[cnt] += w[stack[top]];
V[cnt] += v[stack[top]];
vis[stack[top]] = 0;
belong[stack[top]] = cnt;
}while(stack[top--] != u);
}
}
void dp(int u){
f[u][W[u]] = V[u];
for(int i = head[u]; i; i = e[i].next){
dp(e[i].to);
for(int j = m; j >= W[u]; --j)
for(int k = W[e[i].to]; j - k >= W[u]; ++k)
f[u][j] = max(f[u][j], f[e[i].to][k] + f[u][j - k]);
}
}
int main(){
scanf("%d%d", &n, &m);
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", &fa[i]);
Add(fa[i], i);
}
if(head[0]) Tarjan(0);
for(int i = 1; i <= n; ++i)
if(!dfn[i])
Tarjan(i);
num = 0;
memset(head, 0, sizeof head);
for(int i = 1; i <= m; ++i)
if(belong[i] != belong[fa[i]])
Add(belong[fa[i]], belong[i]), ++in[belong[i]];
for(int i = 1; i <= cnt; ++i)
if(!in[i]){
Add(cnt + 1, i);
}
dp(cnt + 1);
for(int i = 1; i <= m; ++i)
ans = max(ans, f[cnt + 1][i]);
printf("%d
", ans);
return 0;
}