← 返回题目列表

Codeforces · 2193/H

H. 移除圣杯树

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

大圣杯树在王国中已经矗立了$$$315$$$年。它占用了很大的空间,所以国王伊拉决定尽快摆脱它。树本身是一个非循环、连通、无向图,具有 $$$n$$$ 个顶点,每个顶点都有自己的值 $$$a_v$$$。可以通过以下方式删除树:

  • 令 $$$S_v$$$ 为 $$$v$$$ 的所有剩余邻居的值之和。如果 $$$v$$$ 没有剩余的邻居,则 $$$S_v$$$ 是 $$$0$$$。选择一个顶点 $$$v$$$,使得 $$$a_v$$$ 和 $$$S_v$$$ 奇偶性不同(即,$$$a_v$$$ 是偶数,$$$S_v$$$ 是奇数,或者 $$$a_v$$$ 是奇数,$$$S_v$$$ 是偶数)。如果没有这样的顶点,则停止该过程。
  • 从树中删除顶点 $$$v$$$ 以及与其连接的所有边。
你的任务是确定是否存在一系列删除操作,从而导致圣杯树完全删除(即,树中不会保留任何顶点)。如果存在这样的序列,则按照删除的顺序输出 $$$n$$$ 顶点的序列。如果有多个答案,则输出其中任何一个。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含数字 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 圣杯树中的顶点数。

第二行描述数组 $$$a$$$ ($$$1\le a_i\le 10^9$$$) — 树中顶点的值。

接下来有 ​​$$$n - 1$$$ 行,每行包含 2 个数字 $$$v$$$ 和 $$$u$$$ ($$$1\le v, u\le n, v\neq u$$$),表示顶点 $$$v$$$ 和 $$$u$$$ 通过树中的边连接。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果可以完全删除圣杯树,则输出“YES”。否则,输出“NO”。如果答案为“是”,则输出任何移除序列。

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。

示例

输入
复制

5
3
1 2 4
1 2
2 3
4
3 4 2 1
1 2
2 3
3 4
6
9 6 5 1 7 4
1 2
2 3
2 4
3 5
4 6
5
2 1 1 1 2
2 1
3 2
2 4
5 4
5
1 5 3 7 9
1 2
2 3
3 4
4 5

输出
复制

NO
YES
2 3 1 4
NO
YES
1 5 2 3 4
YES
2 4 1 5 3