CF2062E2.The Game (Hard Version)

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是该问题的困难版本。与简单版本的区别在于，此版本需要找到 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

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

说明/提示

第一个测试用例：

若 Cirno 在第一轮选择节点 $1$ 或 $3$ ，Daiyousei 无法操作，因此 Daiyousei 获胜。
若 Cirno 在第一轮选择节点 $2$ 或 $4$ ，Daiyousei 只能选择节点 $3$ ，操作后 Cirno 无法行动，因此 Cirno 获胜。

因此 Cirno 可能选择的节点为 $2$ 和 $4$ 。

第二个测试用例中，无论 Cirno 选择哪个节点，Daiyousei 都无法操作，因此 Daiyousei 获胜。

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

第五个测试用例中，Cirno 可能选择的节点为 $3,4,6,7$ 和 $10$ 。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页