← 返回题目列表

Codeforces · 2152/G

G. 查询丛林

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

Oner 是一名打野者 - 在丛林中猎杀怪物的角色。考虑到他在丛林中看到的树木数量,他沉迷于树木查询问题也就不足为奇了。

给你一棵由 $$$n$$$ 个顶点组成的树,以顶点 $$$1$$$ 为根。每个顶点要么包含怪物,要么不包含怪物。

您想要找到最小整数$$$k$$$,使得存在满足以下条件的$$$k$$$路径:

  • 每条路径必须从根(顶点 $$$1$$$)开始。
  • 每个有怪物的顶点必须至少包含在这些路径之一中。如果顶点是路径的顶点之一(包括其端点),则该顶点被视为包含在路径中。

为了使这个问题更具挑战性,您还必须回答 $$$q$$$ 查询。对于每个查询,您都会获得一个顶点 $$$v$$$。对于每个顶点$$$w$$$ 子树 $$$v$$$的 ,其状态反转——有怪物的开始不包含怪物,不包含怪物的开始包含怪物。每次查询后,您必须使用更新的状态再次解决原始问题。

请注意,查询是 累计,因此每个查询的影响都会延续到未来的查询。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 20\,000$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 250\,000$$$) — 树中的顶点数。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \in \{0, 1\}$$$),代表初始状态。如果$$$a_i = 1$$$,则顶点$$$i$$$包含怪物;如果 $$$a_i = 0$$$,则不会。

接下来的 $$$n-1$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$),描述顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成一棵树。

下一行包含一个整数 $$$q$$$ ($$$0 \le q \le 250\,000$$$) — 查询数。

接下来的 $$$q$$$ 行每行包含一个整数 $$$v_i$$$ ($$$1 \le v_i \le n$$$) — 为第 $$$i$$$ 查询给出的顶点。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$250\,000$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$250\,000$$$。

输出

打印 $$$q + 1$$$ 行。第一行应包含初始状态的最小路径数$$$k$$$。随后的每一行都应包含每个查询后的答案。

示例

输入
复制

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

输出
复制

2
1
1
2
3
1
0
1

注意

测试用例1:

初始状态: 怪物位于顶点 $$$\{2, 4, 5\}$$$。我们需要两条路径:$$$1 \to 7 \to 3 \to 2$$$ 和 $$$1 \to 7 \to 5 \to 4$$$。答案是$$$2$$$。

查询 1 后($$$v=2$$$): 怪物位于顶点$$$\{4, 5\}$$$。我们只需要一条路径,$$$1 \to 7 \to 5 \to 4$$$。答案是$$$1$$$。

查询 2 后($$$v=4$$$): 怪物位于顶点$$$\{5\}$$$。我们只需要一条路径,$$$1 \to 7 \to 5$$$。答案是$$$1$$$。

查询 3 后($$$v=6$$$): 怪物位于顶点$$$\{5, 6\}$$$。我们需要两条路径,$$$1 \to 7 \to 5$$$ 和 $$$1 \to 6$$$。答案是$$$2$$$。

查询 4 之后($$$v=7$$$): 怪物位于顶点 $$$\{2, 3, 4, 6, 7\}$$$。我们需要三个路径,$$$1 \to 6$$$、$$$1 \to 7 \to 5 \to 4$$$ 和 $$$1 \to 7 \to 3 \to 2$$$。答案是$$$3$$$。

下图表示示例输入中的树。

测试用例2:

初始状态: 怪物位于顶点$$$\{2\}$$$。我们需要一条路径:$$$1 \to 2$$$。答案是$$$1$$$。

查询 1 后($$$v=2$$$): 没有怪物。我们需要零路径。答案是$$$0$$$。

查询 2 后($$$v=1$$$): 怪物位于顶点$$$\{1,2\}$$$。我们需要一条路径:$$$1 \to 2$$$。答案是$$$1$$$。