← 返回题目

题库练习 Remove the Grail Tree

← 上一题下一题 →

A16783 | $Remove the Grail Tree$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

伟大的圣杯树已在王国中矗立了 315 年。它占据了大量空间，因此伊拉国王决定尽快将其移除。这棵树本质上是一个包含 $n$ 个顶点的无环、连通、无向图，每个顶点都有一个权值 $a_v$。移除这棵树的规则如下： 1. 设 $S_v$ 为顶点 $v$ 所有剩余相邻顶点的权值之和。若 $v$ 没有剩余相邻顶点，则 $S_v = 0$。选择一个满足 $a_v$ 与 $S_v$ 奇偶性不同的顶点 $v$（即 $a_v$ 为偶数且 $S_v$ 为奇数，或 $a_v$ 为奇数且 $S_v$ 为偶数）；若不存在这样的顶点，则停止操作。 2. 从树中移除顶点 $v$ 及其所有相连的边。 你的任务是判断是否存在一个移除序列，能将这棵圣杯树完全移除（即树中无任何顶点剩余）。若存在这样的序列，输出长度为 $n$ 的移除顺序序列；若有多个合法序列，输出任意一个即可。

输入格式

输入包含多组测试用例。第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的格式如下： 1. 第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示树的顶点数量。 2. 第二行输入一个长度为 $n$ 的数组 $a$（$1 \le a_i \le 10^9$），依次表示每个顶点的权值。 3. 接下来 $n-1$ 行，每行输入两个整数 $v, u$（$1 \le v, u \le n$ 且 $v \neq u$），表示顶点 $v$ 和 $u$ 之间有一条无向边。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例： - 若可以完全移除树，输出 "YES"；否则输出 "NO"（字母大小写任意）。 - 若答案为 "YES"，额外输出一行包含 $n$ 个整数的序列，表示顶点的移除顺序（任意合法序列均可）。

输入输出样例

输入 #1

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

输出 #1

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

C++ 编辑器

输入

输出