AT_cpsco2019_s2_e.Mogu Mogu Gummi

有一棵包含 $N$ 个顶点和 $N-1$ 条边的有根树，其中树根为顶点 $0$。

顶点编号为 $0$ 到 $N-1$，边编号为 $1$ 到 $N-1$。边 $i$ 是连接顶点 $i$ 和 $p_i$ 的无向边，其硬度为 $H_i$。

你需要通过以下操作尽可能多地将这棵树分成多个连通分量：

• 选择一个不为根 $0$ 的顶点 $X$，并用力拉拽使其远离根 $0$。
• 连接根 $0$ 和顶点 $X$ 的路径上的所有边的硬度会减 $1$。
• 硬度减少到 $0$ 的边将从树中断开并消失。
• 与根不连通的顶点将不能再次被选择。

请问，通过重复上述步骤，最多可以将树分成多少个连通分量？

输入以以下格式给出：

$ N $ $ p_1 $ $ H_1 $ $ p_2 $ $ H_2 $ $ : $ $ p_{N-1} $ $ H_{N-1} $

输出经过操作后，树中最多能形成的连通分量的数量。

• $2 \le N \le 5000$
• $0 \le p_i$
• $1 \le H_i \le 10^9$
• 所有输入均为整数。

本题有部分分数的设置：

• 对于满足 $N \le 300$ 的输入，若解答正确则可获得 $500$ 分。

样例解释 1

如果总共选择顶点 $1$ 或 $2$ 选择 $10$ 次，第 $1$ 条边便会断裂，此时树被分成了两个连通分量：$\{0\}, \{1, 2\}$。

样例解释 2

更新后：若选择顶点 $4$ 两次，随后选择顶点 $3$ 三次，可以将树分解为四个连通分量：$\{0\}, \{1, 2\}, \{3\}, \{4\}$。

本翻译由 AI 自动生成