← 返回题目列表

AtCoder · awc0095_e

E. 商店街的商店

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

分数: 433 分

问题陈述

一个城镇有 N 由以下连接的交叉路口 N - 1 道路。任何两个交叉路口都可以通过沿着一条唯一路径(即交叉路口和道路形成树结构)的道路相互到达。

的 距离 交叉路口之间 a 和交叉路口 b 定义为从 a to b。特别是距交叉路口的距离 a 本身就是 0.

最初,任何十字路口都没有商店。在一段时间内 Q 天,当天 i (1 \leq i \leq Q),十字路口新开了一家商店 C_i。任何十字路口的商店都不会营业多次。商店一旦开业,就会无限期地继续经营。

当青木站在镇上的某个路口时,如果恰好有 1 距离内的商店 R 或更少,因为他可以完全拥有那家商店。

对于每一天,确定当天结束时青木会感到快乐的交叉点数量。即求交点的个数 x 使得距离内的商店数量 R 从交叉路口 x 正是 1。请注意,如果相交 x 本身有一个商店(距离 0),也算在店铺之中。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq N
  • N + Q \leq 2 \times 10^5
  • 1 \leq R \leq 20
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • 给定的图是一棵树
  • 1 \leq C_i \leq N
  • 全部 C_i 是不同的
  • 所有输入值均为整数

输入

N Q R
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
C_1
C_2
\vdots
C_Q
  • 第一行包含交叉点的数量 N,天数 Q,以及距离限制 R,用空格分隔。
  • 以下 N - 1 行每行包含 u_i 和 v_i 用空格隔开,表示有道路连接路口 u_i 和交叉路口 v_i.
  • 后续 Q 行每行包含 C_i, 当天新开店的路口号 i.

输出

A_1
A_2
\vdots
A_Q

关于 i第行,输出 A_i,距离内商店数量的路口数量 R 正是 1,在一天结束时 i.


示例输入 1

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

示例输出 1

3
3
3

示例输入 2

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

示例输出 2

6
0
0
0

示例输入 3

15 8 2
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
6 11
6 12
7 13
13 14
13 15
8
12
5
14
1
10
7
3

示例输出 3

4
8
9
13
8
7
4
2

示例输入 4

40 20 4
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
7 14
7 15
8 16
9 17
10 18
10 19
11 20
12 21
13 22
14 23
15 24
16 25
17 26
18 27
19 28
20 29
21 30
22 31
23 32
24 33
25 34
26 35
27 36
28 37
29 38
30 39
31 40
38
34
22
5
27
15
40
1
19
30
8
36
24
12
3
33
10
29
6
17

示例输出 4

5
10
16
13
15
19
17
8
7
5
4
4
3
3
2
2
0
0
0
1

示例输入 5

1 1 20
1

示例输出 5

1