E - Shops in the Shopping Street Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

ある町には N 個の交差点があり、N - 1 本の道路でつながっています。どの 2 つの交差点の間も、道路をたどってちょうど 1 通りの経路で行き来できます（すなわち、交差点と道路は木構造をなしています）。

交差点 a と交差点 b の 距離 を、a から b へ行くために通る道路の本数と定めます。特に、交差点 a から交差点 a 自身への距離は 0 です。

最初、どの交差点にもお店はありません。

Q 日間にわたって、i 日目 (1 \leq i \leq Q) には交差点 C_i に新たにお店がオープンします。同じ交差点に 2 回以上お店がオープンすることはありません。一度オープンしたお店は、その後もずっと営業し続けます。

青木君は町のどこかの交差点に立っているとき、距離 R 以下にあるお店がちょうど 1 軒だけならば、そのお店を独り占めできて嬉しいと感じます。

各日の終わりにおいて、青木君が嬉しいと感じる交差点の個数を求めてください。すなわち、交差点 x からの距離が R 以下であるお店の数がちょうど 1 であるような交差点 x の個数を求めてください。ただし、交差点 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
  • 1 行目には、交差点の個数 N、日数 Q、距離の上限 R がスペース区切りで与えられます。
  • 続く N - 1 行のうち i 行目には、交差点 u_i と交差点 v_i を結ぶ道路があることを表す u_i と v_i がスペース区切りで与えられます。
  • その後の Q 行のうち i 行目には、i 日目に新たにお店がオープンする交差点の番号 C_i が与えられます。

出力

A_1
A_2
\vdots
A_Q

i 行目には、i 日目の終わりにおいて、距離が R 以下であるお店がちょうど 1 軒である交差点の個数 A_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

Score : 433 pts

Problem Statement

A town has N intersections connected by N - 1 roads. Any two intersections can be reached from each other by following roads along exactly one unique path (that is, the intersections and roads form a tree structure).

The distance between intersection a and intersection b is defined as the number of roads traversed to travel from a to b. In particular, the distance from intersection a to itself is 0.

Initially, there are no shops at any intersection. Over a period of Q days, on day i (1 \leq i \leq Q), a new shop opens at intersection C_i. No intersection will have a shop open more than once. Once a shop opens, it continues to operate indefinitely.

When Aoki is standing at some intersection in the town, he feels happy if there is exactly 1 shop within distance R or less, because he can have that shop all to himself.

For each day, determine the number of intersections where Aoki would feel happy at the end of that day. That is, find the number of intersections x such that the number of shops within distance R from intersection x is exactly 1. Note that if intersection x itself has a shop (distance 0), it is also counted among the shops.

Constraints

  • 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
  • The given graph is a tree
  • 1 \leq C_i \leq N
  • All C_i are distinct
  • All input values are integers

Input

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
  • The first line contains the number of intersections N, the number of days Q, and the distance limit R, separated by spaces.
  • The following N - 1 lines each contain u_i and v_i separated by a space, indicating that there is a road connecting intersection u_i and intersection v_i.
  • The subsequent Q lines each contain C_i, the number of the intersection where a new shop opens on day i.

Output

A_1
A_2
\vdots
A_Q

On the i-th line, output A_i, the number of intersections where the number of shops within distance R is exactly 1, at the end of day i.

Sample Input 1

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

Sample Output 1

3
3
3

Sample Input 2

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

Sample Output 2

6
0
0
0

Sample Input 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

Sample Output 3

4
8
9
13
8
7
4
2

Sample Input 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

Sample Output 4

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

Sample Input 5

1 1 20
1

Sample Output 5

1