← 返回题目列表

AtCoder · awc0033_c

C. 谣言的传播

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

分数: 366 分

问题陈述

有 N 高桥学校的学生,编号为 1 to N. M 给出学生之间的友谊关系,其中 i第 好友关系表明该学生 u_i 和学生 v_i 彼此是朋友(友谊是双向的)。请注意,相同的友谊关系不会出现多次,并且没有学生会与自己成为朋友。

最初,仅 K 学生 C_1, C_2, \ldots, C_K 知道某个谣言。从这个初始状态开始,谣言按照以下规则一天天传播:

> 评价: 每天开始时,为每个还不知道谣言的学生统计他们当前知道谣言的朋友数量。如果这个数字至少是 T,该学生将在当天结束时重新了解到谣言。

>

> 同时更新: 如果多名学生在某一天新了解到该谣言,则他们会在当天结束时同时了解到该谣言。即使某个学生在一天结束时新了解到谣言,这也不影响当天其他学生的评价。

这个过程每天都会重复,直到没有新学生知道这个谣言。

确定最终知道该谣言的学生人数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq T \leq N
  • 1 \leq C_i \leq N (1 \leq i \leq K)
  • 全部 C_i 是不同的
  • 1 \leq u_i < v_i \leq N (1 \leq i \leq M)
  • 所有对 (u_i, v_i) 是不同的
  • 所有输入值均为整数

输入

N M K T
C_1 C_2 \ldots C_K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • 第一行包含学生人数 N, 好友数量 M,初步知道该谣言的学生人数 K,以及谣言传播所需的好友数量阈值 T,用空格分隔。
  • 第二行包含学号 C_1, C_2, \ldots, C_K 最初知道谣言的人,以空格分隔。
  • 从第三行到 (M + 2)第行, M 给出了友谊关系。
  • 的 (2 + i)第行 (1 \leq i \leq M) 包含学生编号 u_i 和 v_i 的 i第一个好友关系,以空格分隔。

输出

在一行中打印传播收敛后知道谣言的学生数量。


示例输入 1

5 6 2 2
1 2
1 3
2 3
1 4
2 4
3 5
4 5

示例输出 1

5

示例输入 2

6 5 2 2
1 6
1 2
2 3
3 4
4 5
5 6

示例输出 2

2

示例输入 3

10 16 2 2
1 2
1 3
2 3
1 4
2 4
3 5
4 5
3 6
4 6
5 7
6 7
5 8
6 8
7 9
8 9
7 10
8 10

示例输出 3

10

示例输入 4

18 30 3 2
1 2 3
1 4
2 4
2 5
3 5
4 6
5 6
4 7
5 7
6 8
7 8
6 9
7 9
8 10
9 10
8 11
9 11
10 12
11 12
10 13
11 13
12 14
13 14
3 15
5 15
14 16
15 16
14 17
15 17
16 18
17 18

示例输出 4

18

示例输入 5

1 0 1 1
1

示例输出 5

1