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 自动生成**