AT_jsc2019_final_g.Important Bridges

AtCoder 株式会社由 $N$ 个编号为 $0$ 到 $N-1$ 的岛屿组成。这些岛屿通过 $N-1$ 座编号为 $0$ 到 $N-2$ 的桥相连。第 $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$ 天中午时至少有一家酒店处于营业状态。

如果在第 $j$ 天中，存在两个正在营业的岛屿 $a$ 和 $b$，且从 $a$ 前往 $b$ 必须经过第 $i$ 座桥，则称第 $i$ 座桥在第 $j$ 天是重要的。

请计算每一座桥在 $Q$ 天中有多少天是重要的。

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

$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$ 天中是重要的天数。

限制条件

• $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

例如，第 $2$ 天中午营业的酒店位于岛屿 $0,2,4$，这一天重要的桥为桥 $1,2,3$。

由 ChatGPT 4.1 翻译