这是问题的困难版本。 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$$$。