CF2062E2 The Game (Hard Version)

这是该问题的困难版本。与简单版本的区别在于，此版本需要找到 Cirno 在第一轮可能选择的所有节点。仅当解决所有版本的问题时方可进行 hack。 Cirno 和 Daiyousei 正在玩一个以节点 $1$ 为根的 $n$ 节点树 $^{\text{∗}}$ 游戏，其中第 $i$ 个节点的权值为 $w_i$。她们轮流行动，Cirno 先手。 每一轮中，假设对手在上轮选择了节点 $j$，当前玩家必须选择一个未被删除的节点 $i$ 满足 $w_i > w_j$，并删除节点 $i$ 的子树 $^{\text{†}}$。特别地，在第一轮中 Cirno 可以选择任意节点并删除其子树。 无法操作的玩家获胜，双方都希望自己获胜。请找出 Cirno 在第一轮可能选择的所有节点，使得在双方都采取最优策略时她能获胜。 $^{\text{∗}}$ 树是一个无环的连通图。 $^{\text{†}}$ 若从根节点 $1$ 到节点 $u$ 的所有路径都必须经过节点 $i$，则称节点 $u$ 属于节点 $i$ 的子树。

第一行输入包含一个整数 $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$。

对于每个测试用例，输出一行： - 若 Cirno 能获胜，首先输出一个整数 $k$ 表示可能选择的节点数量，接着按升序输出所有可能的节点。 - 否则输出 "0"（不带引号）。

第一个测试用例： 1. 若 Cirno 在第一轮选择节点 $1$ 或 $3$，Daiyousei 无法操作，因此 Daiyousei 获胜。 2. 若 Cirno 在第一轮选择节点 $2$ 或 $4$，Daiyousei 只能选择节点 $3$，操作后 Cirno 无法行动，因此 Cirno 获胜。 因此 Cirno 可能选择的节点为 $2$ 和 $4$。 第二个测试用例中，无论 Cirno 选择哪个节点，Daiyousei 都无法操作，因此 Daiyousei 获胜。 第三和第四个测试用例中，Cirno 唯一可能选择的节点是 $2$。 第五个测试用例中，Cirno 可能选择的节点为 $3,4,6,7$ 和 $10$。 翻译由 DeepSeek R1 完成