这是问题的简单版本。版本之间的区别在于,在这个版本中,你只需要找到Cirno可能选择的可能节点之一。只有解决了该问题的所有版本,您才能破解。
Cirno 和 Daiyousei 正在玩一个游戏,树 $$$^{\text{∗}}$$$ 共有 $$$n$$$ 个节点,根节点为 $$$1$$$。第 $$$i$$$ 节点的值为 $$$w_i$$$。他们轮流玩游戏;琪露诺先行。
每回合中,假设对手在上回合选择$$$j$$$,则玩家可以选择任意剩余满足$$$w_i>w_j$$$的节点$$$i$$$,并删除节点$$$i$$$的子树$$$^{\text{†}}$$$。特别是,Cirno 可以在第一轮选择任何节点并删除其子树。
最先不会操作的玩家获胜,他们都希望获胜。找到琪露诺可能选择的节点之一,这样如果两个节点都发挥最佳,她就获胜。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 输入测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$) — 树中的节点数。
第二行包含 $$$n$$$ 整数 $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le n$$$) — 每个节点的值。
接下来的 $$$n-1$$$ 行包含树的边缘。第 $$$i$$$ 行包含两个整数 $$$u_i,v_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$) — 连接 $$$u_i$$$ 和 $$$v_i$$$ 的边。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$4\cdot 10^5$$$。
输出
对于每个测试用例,打印一行。
如果琪露诺赢得了游戏,则打印她在第一回合中可能选择的任何可能的节点。
否则,打印“0”(不带引号)。
示例
输入 #1
5 4 2 2 4 3 1 2 1 3 2 4 5 1 2 3 4 5 1 2 2 3 3 4 4 5 3 1 2 3 1 2 1 3 5 3 1 3 4 5 1 2 2 3 3 4 4 5 10 1 2 3 2 4 3 3 4 4 3 1 4 4 6 7 4 6 9 6 5 7 8 1 2 2 3 2 10
输出 #1
2 0 2 2 10
注意
在第一个测试用例中:
1.如果琪露诺第一回合选择$$$1$$$或$$$3$$$,大妖星无法出手,大妖星获胜。
2.如果琪露诺第一回合选择$$$2$$$或$$$4$$$,大妖星只能选择$$$3$$$,但之后琪露诺无法出手,琪露诺获胜。
因此,琪露诺可以选择的所有可能节点是$$$2$$$和$$$4$$$。
在第二个测试用例中,无论琪露诺选择哪个节点,大妖星都无法采取行动,因此大妖星获胜。
在第三个和第四个测试用例中,Cirno 在第一回合中唯一可能选择的节点是 $$$2$$$。
在第五个测试用例中,Cirno在第一回合中可能选择的所有可能节点是$$$3,4,6,7$$$和$$$10$$$。