4140. 终末鸟

【题目背景】

注：本题读入和输出量较大，建议使用快读快写，10s 时限是因为 COGS 的逆天评测姬，和乱搞写法没关系

数据过弱，部分点可以用错误的复杂度日过去，但是正解一定是 O(n) 的

大鸟的大眼掩盖着光源...

高鸟的长臂紧握着时间...

小喙的低语永不停歇...

很久很久以前，在一片温暖又繁茂的森林里住着三只快乐的鸟儿

小鸟决定用它的喙来惩罚那些犯了错的动物们

长有许多眼睛的大鸟监视着森林并寻找入侵者。大鸟的眼睛能看到很远的地方，甚至能看到我们看不见的东西

为了维持森林的和平，高鸟审判着动物们的罪孽，它的天平能够绝对公正地衡量任何罪恶

在嘈杂的哭喊中，在惊恐的尖叫中，有人大声喊道：“是那个怪物！黑暗的森林里有一个可怕的大怪物！”

大鸟那可以看到数百里外的眼睛，现在再也看不见了...

小鸟那可以吞噬一切动物的巨口，现在再也张不开了...

高鸟那一直仰望着星空的头颅，现在再也抬不起来了...

三只鸟——现在成为了一只，四处张望着寻找那个怪物，可没有任何结果。那儿已经什么都没有了，没有动物，没有日月，也没有怪物。只有那只鸟，还有那片黑暗的森林...

【题目描述】

脑叶公司中共有 n 个部门，其间用 n - 1 条员工走廊两两相连。

某天，终末鸟逃离了收容，他的大眼遮掩着光芒。

当终末鸟逃出收容后，他会立刻使一些部门陷入“熄灯”状态。

终末鸟可以释放技能，使得一个部门进入“熄灯”状态并随机挑选一名员工诱惑并杀害。

为了控制损失以及镇压终末鸟，作为主管的你需要随时了解“熄灯”状态的部门的连通块个数。

【输入格式】

第一行一个整数 n 表示部门个数。

接下来 n - 1 行每行两个整数 x，y，表示一条员工走廊连接 x 部门和 y 部门，保证所有的部门连通。

接下来一行 n 个整数，表示终末鸟刚出逃时所有部门的状态，若第 i 个数为 0，表示第 i 个部门未“熄灯”，若为 1 表示第 i 个部门“熄灯”。

接下来一行一个整数 q 表示终末鸟一共释放 q 次技能。

接下来 q 行每行一个整数 x，若 x 部门未“熄灯”，表示终末鸟将会释放技能使得部门 x 进入“熄灯”状态。或者该部门已经“熄灯”，终末鸟的技能结束，部门 x 脱离“熄灯”状态。

【输出格式】

一共 q + 1 行。

第一行一个整数表示终末鸟刚出逃时所有“熄灯”部门的连通块个数

接下来 q 行每行一个整数表示每次技能后所有“熄灯”部门的连通块个数

【样例输入】

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

【样例输出】

2
1
2
1

【样例说明】

一开始部门 3，4，6 “熄灯”，连通块有 3 - 6， 4

第一次释放技能 部门一陷入 “熄灯” 连通块只剩 1 - 3 - 6 - 4

第二次释放技能 部门一不再 “熄灯” 连通块有 3 - 6， 4

第三次释放技能 部门四不再 “熄灯” 连通块有 3 - 6

大样例

pretest2 与测试点 3 范围一致

pretest3 与测试点 4 范围一致

pretest4 与测试点 5 ~ 7 范围一致

【数据规模与约定】

测试点1 ~ 2 : n,q <= 1e3

测试点3：n,q <= 2e5，保证图为菊花图

测试点4：n,q <= 2e5，保证图为一条链

测试点5 ~ 7：n,q <= 2e5

测试点8 ~ 10：n,q <= 1e7

【来源】

脑叶公司真好玩