The Game (Hard Version)
Contest: Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)
Difficulty rating: 3000
Tags: data structures, dfs and similar, games, graphs, implementation, trees

This is the hard version of the problem. The difference between the versions is that in this version, you need to find all possible nodes Cirno may choose. You can hack only if you solved all versions of this problem.

Cirno and Daiyousei are playing a game with a tree$$$^{\text{∗}}$$$ of $$$n$$$ nodes, rooted at node $$$1$$$. The value of the $$$i$$$-th node is $$$w_i$$$. They take turns to play the game; Cirno goes first.

In each turn, assuming the opponent chooses $$$j$$$ in the last turn, the player can choose any remaining node $$$i$$$ satisfying $$$w_i>w_j$$$ and delete the subtree$$$^{\text{†}}$$$ of node $$$i$$$. In particular, Cirno can choose any node and delete its subtree in the first turn.

The first player who can not operate wins, and they all hope to win. Find all possible nodes Cirno may choose in the first turn so that she wins if both of them play optimally.

Input format:
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.

The next $$$n-1$$$ lines contain the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i,v_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$) — an edge connecting $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the given edges form a tree.

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

Output format:
For each test case, print one line.

If Cirno wins the game, print several integers. The first integer $$$k$$$ represents the number of possible nodes she may choose in the first turn. The other $$$k$$$ integers are all possible nodes in increasing order.

Otherwise, print "0" (without quotes).

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
In the first test case:

1. If Cirno chooses $$$1$$$ or $$$3$$$ in the first turn, Daiyousei cannot make a move, so Daiyousei wins.
2. If Cirno chooses $$$2$$$ or $$$4$$$ in the first turn, Daiyousei can only choose $$$3$$$, but after it Cirno cannot make a move, so Cirno wins.

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

In the second test case, regardless of which node Cirno chooses, Daiyousei cannot make a move, so Daiyousei wins.

In the third and fourth test case, the only possible node Cirno may choose in the first turn is $$$2$$$.

In the fifth test case, all possible nodes Cirno may choose in the first turn are $$$3,4,6,7$$$ and $$$10$$$.

Example input:
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

Example output:
2 2 4
0
1 2
1 2
5 3 4 6 7 10

Editorial:
In the first round, the node $$$u$$$ chosen by Cirno must satisfy: there exists a node $$$v$$$ outside the subtree of $$$u$$$ such that $$$w_v > w_u$$$. If no such node exists, then Cirno will lose.
Similar to Cirno's strategy in E1, if Daiyousei can choose a node such that Cirno can still make a move after the operation, then Daiyousei only needs to select the node with the largest $$$w_u$$$ among these nodes to win. Therefore, Cirno must ensure that she cannot make a move after Daiyousei's operation.
Enumerate the node $$$u$$$ chosen by Daiyousei, then the node $$$v$$$ chosen by Cirno must satisfy:
Either for all nodes $$$x$$$ with $$$w_x > w_u$$$, $$$x$$$ must be within the subtree of $$$u$$$ or $$$v$$$. In other words, $$$v$$$ must be an ancestor of the lca of all $$$x$$$ outside the subtree of $$$u$$$ that satisfy $$$w_x > w_u$$$ (denoted as $$$g(u) = v$$$).
Or $$$v$$$ must prevent Daiyousei from choosing this $$$u$$$. In other words, either $$$w_v \ge w_u$$$, or $$$u$$$ is within the subtree of $$$v$$$.
Therefore, $$$v$$$ must satisfy that for all $$$w_u > w_v$$$, either $$$u$$$ is within the subtree of $$$v$$$, or $$$g(u)$$$ is within the subtree of $$$v$$$, and this is a necessary and sufficient condition.
To compute $$$g(u)$$$: Enumerate $$$u$$$ from largest to smallest, which is equivalent to computing the lca of all enumerated nodes outside the subtree. This can be achieved in several ways:
1. Use a segment tree or Fenwick tree to maintain the lca of intervals on the dfs order, where the outside of the subtree corresponds to the prefix and suffix of the dfs order. Depending on the method of lca implementation, the complexity could be $$$O(n\log^2n)$$$ or $$$O(n\log n)$$$.
2. Since the lca of a set of nodes is equivalent to the lca of the node with the smallest dfs order and the node with the largest dfs order, std::set can be used to maintain such nodes.
To determine the condition that $$$v$$$ must satisfy, also enumerate from largest to smallest. For a node $$$u$$$, if there exists a corresponding $$$g(u)$$$, then add one to the chain from $$$u$$$ to $$$1$$$, add one to the chain from $$$g(u)$$$ to $$$1$$$, and subtract one from the chain from $$$lca(u,g(u))$$$ to $$$1$$$. This way, all nodes that satisfy the condition are exactly incremented by one. It is only necessary to check whether the current value of $$$v$$$ is equal to the number of $$$u$$$. Depending on the implementation, the complexity could be $$$O(n\log^2n)$$$ or $$$O(n\log n)$$$.
Additionally, there exists a method that does not require computing the lca.