← 返回题目列表

Codeforces · 2062/E2

E2. 游戏(困难版)

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

这是问题的困难版本。 The difference between the versions is that in this version, you need to find all possible nodes Cirno may choose.只有解决了该问题的所有版本,您才能破解。

Cirno 和 Daiyousei 正在玩一个游戏,树 $$$^{\text{∗}}$$$ 共有 $$$n$$$ 个节点,根节点为 $$$1$$$。第 $$$i$$$ 节点的值为 $$$w_i$$$。他们轮流玩游戏;琪露诺先行。

每回合中,假设对手上一回合选择$$$j$$$,则玩家可以选择任意剩余满足$$$w_i>w_j$$$的节点$$$i$$$,并删除节点$$$i$$$的子树$$$^{\text{†}}$$$。 In particular, Cirno can choose any node and delete its subtree in the first turn.

第一个不会操作的玩家获胜,他们都希望获胜。找到琪露诺在第一回合中可能选择的所有可能节点,以便在双方都发挥最佳的情况下获胜。

输入

The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of input test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$) — the number of nodes in the tree.

The second line contains $$$n$$$ integers $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le n$$$) — the value of each node.

接下来的 $$$n-1$$$ 行包含树的边缘。第 $$$i$$$ 行包含两个整数 $$$u_i,v_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$) — 连接 $$$u_i$$$ 和 $$$v_i$$$ 的边。保证给定的边形成一棵树。

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4\cdot 10^5$$$.

输出

对于每个测试用例,打印一行。

如果 Cirno 赢得了比赛,则打印几个整数。第一个整数 $$$k$$$ 表示她在第一轮中可能选择的节点数。 The other $$$k$$$ integers are all possible nodes in increasing order.

否则,打印“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 2 4
0
1 2
1 2
5 3 4 6 7 10

注意

在第一个测试用例中:

1. If Cirno chooses $$$1$$$ or $$$3$$$ in the first turn, Daiyousei cannot make a move, so Daiyousei wins.
2.如果琪露诺第一回合选择$$$2$$$或$$$4$$$,大妖星只能选择$$$3$$$,但之后琪露诺无法出手,琪露诺获胜。

Therefore, all possible nodes Cirno may choose are $$$2$$$ and $$$4$$$.

在第二个测试用例中,无论琪露诺选择哪个节点,大妖星都无法出手,所以大妖星获胜。

在第三个和第四个测试用例中,Cirno 在第一回合中唯一可能选择的节点是 $$$2$$$。

在第五个测试用例中,Cirno在第一回合中可能选择的所有可能节点是$$$3,4,6,7$$$和$$$10$$$。