P12749 [POI 2017 R2] 罢工 Strikes

翻译来自于 [LibreOJ](https://loj.ac/p/5057)。

**题目译自 [XXIV Olimpiada Informatyczna — II etap](https://sio2.mimuw.edu.pl/c/oi24-2/dashboard/) [Strajki](https://szkopul.edu.pl/problemset/problem/lR_LabSUC2n7EMmDHpw-wk_b/statement/)** 比特尼亚的居民以热情奔放和热爱民主著称，与崇尚君主制、平静安宁的拜托尼亚截然不同。当他们对政府决定（如增加字节位数）不满，或支持某理念（如内存与缓存平等）时，便会走上街头，发起罢工。 比特尼亚有 $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$。

**样例 1 解释**  图示为城市 $2$ 和 $7$ 发起罢工后的比特尼亚通信网络，网络分裂为三部分。 **附加样例** 1. $n=2, m=10$，两城市交替改变罢工状态。 2. $n=1000, m=n$，路网为一条链，每城市依次发起罢工。 3. $n=500000$，路网为一条链，偶数编号城市依次发起罢工，随后按同顺序结束。 路网为一条链，指对于 $a=1, \ldots, n-1$，城市 $a$ 和 $a+1$ 相连。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n, m \leq 1000$ | $24$ | | $2$ | $n, m \leq 500000$，路网为一条链 | $17$ | | $3$ | $n, m \leq 500000$，输入全为正数 | $17$ | | $4$ | $n, m \leq 500000$ | $42$ |