P14471 [集训队互测 2025] 火花

:::align{center} $\textbf{愛し方さえも　君の匂いがした}$ 即便是爱你的时候 也散发你的味道 $\textbf{歩き方さえも　その笑い声がした}$ 甚至连走路的时候 也充斥你那样的笑声 :::

- 有一棵 $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 \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 分）：无特殊限制。