配点 : 600 点
問題文
N 頂点 N-1 一种形状像有根树的软糖,由侧面组成。 有 G 。
在顶点 0 从 N-1 号码位于侧面。 它的编号为 1 从 N-1 。
根是顶点 0 。侧面 i 是顶点 它是一条连接 i 和 p_i 的无向边,其硬度为 H_i 。
您可以重复以下步骤来制作这款软糖 我正在尝试将 G 拆分为更多连接的组件。
- 根 0 之外 1 顶点 选择 X 并root 用双手拉 0 和 X 。 连接
- 根 0 和 X 的路径上所有边的硬度为 1 减少。
- 硬度 所有变成 0 的边缘都被撕掉并消失。
- 结果,不再连接到根的顶点是 2 我无法选择。
重复操作后, 求G 的最大连通分量数。
制約
- 2 \le N \le 5000
- 0 \le p_i < i
- 1 \le H_i \le 10^9
- 所有输入均为整数。 如果您正确回答满足
部分点
针对此问题设置了部分分数。
- N \le 300 的输入, 输出500 点。
入力
输入是按以下格式从标准输入给出的。
N
p_1 H_1
p_2 H_2
:
p_{N-1} H_{N-1}
出力
重复操作后, 求G 的最大连通分量数。 总和
入力例 1
3 0 10 1 20
出力例 1
2
頂点 1 或 2 如果您选择 10 次,1 面将被撕裂,并且无法进行进一步的操作。
此时,G 是 小于或等于 \{0\},\{1,2\} 它分为 2 连接组件。
入力例 2
5 0 5 1 10 1 3 2 2
出力例 2
4
(10:40 更新) 頂点 4 的 2 选择时间、顶点 它分为 3 的 3 次,\{0\},\{1,2\},\{3\},\{4\} 它分为 4 连接组件。
入力例 3
10 0 12 1 6 1 3 1 6 3 7 4 2 4 8 5 5 5 1
出力例 3
6