题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIV Olimpiada Informatyczna — II etap Strajki

比特尼亚的居民以热情奔放和热爱民主著称，与崇尚君主制、平静安宁的拜托尼亚截然不同。当他们对政府决定（如增加字节位数）不满，或支持某理念（如内存与缓存平等）时，便会走上街头，发起罢工。

比特尼亚有 $n$ 座城市。每座城市的居民独立决定是否发起或结束罢工。罢工期间，城市陷入瘫痪，无法进出。遗憾的是，国家的路网设计极简，任意两城市间仅有一条路径。这使得罢工成为非罢工城市居民的交通噩梦。罢工导致通信网络分裂为若干部分，只有同一部分的非罢工城市间可通达。

作为比特尼亚的交通监察专员，你需编写程序，根据当前罢工信息，计算通信网络分裂成的部分数量。

比特尼亚的所有道路均为双向，起点和终点均为城市。

输入格式

第一行包含一个整数 $n$ $(n \geq 2)$，表示比特尼亚的城市数量。城市编号为 $1$ 至 $n$。

接下来的 $n-1$ 行描述道路，每行包含两个整数 $a, b$ $(1 \leq a < b \leq n)$，表示城市 $a$ 和 $b$ 间存在一条道路。任意两城市间存在一条由若干道路组成的路径。

下一行包含一个整数 $m$ $(m \geq 1)$，表示罢工信息的数量。

接下来的 $m$ 行，每行包含一个整数 $z$ $(1 \leq |z| \leq n)$。若 $z > 0$，表示城市 $z$ 发起罢工；若 $z < 0$，表示城市 $-z$ 结束罢工。

保证每座城市同时至多有一个罢工：若城市在罢工，不可再次发起；若未在罢工，不可结束。初始时无城市罢工。

输出格式

输出 $m$ 行，第 $i$ $(1 \leq i \leq m)$ 行包含一个整数，表示第 $i$ 条罢工信息后，通信网络分裂成的部分数量。若所有城市均在罢工，输出 $0$。

7
1 2
2 3
2 4
4 5
4 6
6 7
4
2
7
4
-2

3
3
4
3

提示

样例 1 解释

图示为城市 $2$ 和 $7$ 发起罢工后的比特尼亚通信网络，网络分裂为三部分。

附加样例

1. $n=2, m=10$，两城市交替改变罢工状态。
2. $n=1000, m=n$，路网为一条链，每城市依次发起罢工。
3. $n=500000$，路网为一条链，偶数编号城市依次发起罢工，随后按同顺序结束。

路网为一条链，指对于 $a=1, \ldots, n-1$，城市 $a$ 和 $a+1$ 相连。

详细子任务附加限制及分值如下表所示。