题目描述
- 有一棵 $n$ 个点、根为 $1$ 的树。第 $i$ 个点上有 $c_i$ 个物品，权值均为 $v_i$。
- 需要先选择 $t$ 个不同的点，对于选的每个点，在它的每个祖先（包括自己）上各取一个物品。
- 本题保证 $\boldsymbol{t \lt c_i}$，因此不会存在没有物品可取的情况。
- 接下来可以取至多 $k$ 个物品，要求所有在这一步被取了物品的点形成一个含根的连通块。
- 最大化整个过程中取的物品权值之和。
输入格式
- 第一行三个整数 $n, k, t$。
- 接下来 $n$ 行，每行两个正整数分别表示 $c_i$ 和 $v_i$。
- 最后一行 $n - 1$ 个正整数，第 $i$ 个正整数表示点 $(i + 1)$ 在树上的父亲 $\mathrm{fa}_{i + 1}$。
输出格式
- 一行，输出一个非负整数，表示最大的权值和。
样例
样例 1 输入
4 4 1 2 1 2 1 2 5 2 1 1 1 2
样例 1 输出
15
数据范围
对于所有数据：$1 \leq n, k \leq 10^4$，$0\leq t \leq n$，$\boldsymbol{t \lt c_i} \leq 10^9$，$1\leq v_i \leq 10^9$，$\mathrm{fa}_i \lt i$，$nk(t+1)\leq 10^7$。
- 子任务 1（10 分）：$n, k, t \leq 10$。
- 子任务 2（20 分）：$t = 0$。
- 子任务 3（15 分）：$n k (t + 1) \leq 10^6$。
- 子任务 4（25 分）：$n k (t + 1) \leq 5 \times 10^6$。
- 子任务 5（30 分）：无特殊限制。