← 返回题目列表

AtCoder · jsc2019_final_g

G. 重要桥梁

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

配点 : 1200 点

問題文

AtCoder有限公司 编号至0 假设一直下雨,直到 N-1 编号最多为 N 一家由岛屿组成的公司。 这些岛屿是 它们通过0 假设一直下雨,直到 N-2 编号最多为 N-1 桥连接。 桥 i 是一座岛屿 A_i 和岛屿 B_i 双向连接。 过桥可以到达任何岛屿。

所有岛屿都有酒店。 不过,目前所有酒店均已关闭。 因此,负责AtCoder旅游部门的高桥先生决定 Q 我们已制定重新开放酒店的计划并暂停酒店运营几天。 具体来说,i (0 \leq i \leq Q-1)在第一天早上,发生以下情况:

  • 島 X_i 如果酒店关闭,酒店将重新营业。
  • 島 X_i 如果酒店营业,该酒店将关闭。

请注意,所有 i (0 \leq i \leq Q-1),i 当天中午营业的酒店 1 保证至少有一个。

橋 i 是 时间保证在 j 当天重要的意思是:

  • j 酒店当天中午营业 2 角岛 a,b 是一座岛屿 a 辛岛 一座可以去的桥 b 有些事情必须经历 i 。

对于每座桥梁,请标明其重要的日期。 Q 找出天数中有多少天。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i,B_i \leq N-1
  • 过桥可以到达任何岛屿。
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq X_i \leq N-1
  • 全部 i (0 \leq i \leq Q-1),i 当天中午营业的酒店 1 不止一个。
  • 所有输入值都是整数。 输出

入力

输入是按以下格式从标准输入给出的。

N Q
A_0 B_0
A_1 B_1
\vdots
A_{N-2} B_{N-2}
X_0
X_1
\vdots
X_{Q-1}

出力

N-1 行。 i+1 (0 \leq i \leq N-2)线是一座桥。 i 重要的一天是 Q 打印一天有多少天。


入力例 1

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

出力例 1

2
3
3
3

例如,2 酒店当天中午营业的岛屿是 0,2,4 而这一天最重要的桥梁是 Bridge 1,2,3 。


入力例 2

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

出力例 2

9
5
5
2
2
12
6
2
5
9
12
12
12
13