← 返回题目列表

AtCoder · awc0101_c

C. 感染链

中文机器翻译题面 查看原题

分数: 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) 不会被感染,也永远不会被感染。感染按照以下规则以连锁反应传播:

  1. 初次感染: 所有具有正漏洞值的计算机 (D_i > 0)被感染。漏洞值为 0 或更少 (D_i \leq 0)在此阶段没有被感染。然而,他们以后可能会通过下面的规则 2 被感染。
  1. 感染传播(儿童→家长方向): 对于计算机 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,因此这样的计算机不会被此规则感染。仅根据子女的感染状况,在父母被感染的方向发生感染。即使父计算机被感染,也不会导致其子计算机再次被感染。
  1. 重复: 重复规则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