依赖背包

题目描述

$n$ 件物品构成一片森林（根的"父"不存在）。选某件物品必须先选它的直接父件。背包容量 $V$，第 $i$ 件体积 $w_i$、价值 $val_i$。求能装入的最大价值。注意：不选父件时其子树全部不能选；但可以选父件而不选子件。

输入格式

第一行两个整数 $n$ 和 $V$；第二行 $n$ 个整数 $w_i$；第三行 $n$ 个整数 $val_i$；第四行 $n$ 个整数 $fa_i$（$fa_i=0$ 表示无父）。

输出格式

一行一个整数。

数据范围