分数: 366 分
问题陈述
Takahashi 是一个网络的管理员,该网络包括 N 计算机和 1 中央服务器。的 N 计算机编号为 1 to N,中央服务器编号为计算机 0。也就是说,整个网络总共由 N + 1 计算机:计算机 0, 1, \ldots, N.
每台计算机 i (1 \leq i \leq N) 直接连接到父计算机 P_i (0 \leq P_i \leq N, P_i \neq i)。这些连接形成一个树结构 N + 1 顶点植根于中央服务器(计算机 0)。在这个树结构中,有一个 儿童电脑 计算机的 计算机的 v 指计算机 j 满意 P_j = v.
有一天,一种病毒渗透到网络中。每台电脑 i (1 \leq i \leq N) 具有漏洞值 D_i 分配给它。
病毒感染仅针对计算机 1 通过 N。中央服务器(计算机 0) 不会被感染,也永远不会被感染。感染按照以下规则以连锁反应传播:
- 初次感染: 所有具有正漏洞值的计算机 (D_i > 0)被感染。漏洞值为 0 或更少 (D_i \leq 0)在此阶段没有被感染。然而,他们以后可能会通过下面的规则 2 被感染。
- 感染传播(儿童→家长方向): 对于计算机 v (1 \leq v \leq N)尚未被感染,让 a 是受感染子计算机的数量 v,和 b 是未受感染的子计算机的数量 v。如果 a > b 满足,则 v 新感染。无论漏洞值如何,都会做出此决定 D_v 计算机的 v 本身。也就是说,即使 如果满足其子计算机感染状态的条件, D_v \leq 0, v 就会被感染。请注意,对于没有子计算机的计算机, a = b = 0,不满足 a > b,因此这样的计算机不会被此规则感染。仅根据子女的感染状况,在父母被感染的方向发生感染。即使父计算机被感染,也不会导致其子计算机再次被感染。
- 重复: 重复规则2中的确定和感染,直到一轮中没有新计算机被感染。每轮的判定是所有计算机同时进行的,基于 该回合开始时的感染状态。也就是说,如果多台计算机在给定的轮次中新被感染,它们都会同时被感染,并且感染状态在同一轮次中途不会改变。下一轮的决定将基于更新的感染状况。
确定最终被感染的计算机总数。中央服务器(计算机 0) 不会受到感染,因此不应包含在计数中。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq P_i \leq N, P_i \neq i (1 \leq i \leq N)
- 给定的连接形成一个树结构 N + 1 以计算机为根的顶点 0
- -10^9 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数
输入
N P_1 D_1 P_2 D_2 \vdots P_N D_N
- 第一行包含一个整数 N 代表计算机的数量。
- 线 2 通过 N + 1 给出每台计算机的信息。
- 线 1 + i 包含父计算机编号 P_i 计算机的 i 和漏洞值 D_i 计算机的 i,用空格分隔。
输出
在一行中输出最终被感染的计算机总数。
示例输入 1
6 0 -1 1 1 1 2 1 0 2 -5 3 0
示例输出 1
3
示例输入 2
4 0 0 0 -3 0 -1 0 0
示例输出 2
0
示例输入 3
15 0 -5 1 -1 1 -1 1 0 2 1 2 1 2 0 3 -1 3 2 3 0 4 1 4 0 8 1 8 1 8 0
示例输出 3
10
示例输入 4
40 0 -100 1 0 1 -1 1 -1 2 -1 2 -1 2 3 3 -2 3 -2 3 -2 4 1 4 0 4 1 5 0 5 1 5 1 6 -1 6 2 7 0 7 -5 8 1 8 0 8 1 9 -1 9 -1 10 1 10 1 10 0 17 1 17 0 17 1 19 1 19 0 20 -1 20 -1 24 1 24 1 25 0 25 1 34 1
示例输出 4
28
示例输入 5
1 0 -1000000000
示例输出 5
0