← 返回题目列表

Codeforces · 2062/E1

E1. 游戏(简易版)

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

这是问题的简单版本。版本之间的区别在于,在这个版本中,你只需要找到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$$$。