Vertex Pairs
Contest: Educational Codeforces Round 172 (Rated for Div. 2)
Difficulty rating: 2900
Tags: binary search, brute force, data structures, dfs and similar, divide and conquer, greedy, implementation, trees

You are given a tree consisting of $$$2n$$$ vertices. Recall that a tree is a connected undirected graph with no cycles. Each vertex has an integer from $$$1$$$ to $$$n$$$ written on it. Each value from $$$1$$$ to $$$n$$$ is written on exactly two different vertices. Each vertex also has a cost —vertex $$$i$$$ costs $$$2^i$$$.

You need to choose a subset of vertices of the tree such that:

- the subset is connected; that is, from each vertex in the subset, you can reach every other vertex in the subset by passing only through the vertices in the subset;
- each value from $$$1$$$ to $$$n$$$ is written on at least one vertex in the subset.

Among all such subsets, you need to find the one with the smallest total cost of the vertices in it. Note that you are not required to minimize the number of vertices in the subset.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$2n$$$ integers $$$a_1, a_2, \dots, a_{2n}$$$ ($$$1 \le a_i \le n$$$). Each value from $$$1$$$ to $$$n$$$ appears exactly twice.

Each of the next $$$2n-1$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le 2n$$$) — the edges of the tree. These edges form a valid tree.

Output format:
In the first line, print a single integer $$$k$$$ — the number of vertices in the subset.

In the second line, print $$$k$$$ distinct integers from $$$1$$$ to $$$2n$$$ — the indices of the vertices in the chosen subset. The vertices can be printed in an arbitrary order.

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

Note:
The images show the answers to the first two examples. The numbers in parentheses are the values written on the vertices.

In the first example, there are valid subsets such as: $$$[2, 4, 5]$$$ (with a cost of $$$2^2 + 2^4 + 2^5 = 52$$$), $$$[2, 4, 5, 6]$$$ (with a cost of $$$116$$$), $$$[1, 6, 3]$$$ (with a cost of $$$74$$$), $$$[2, 6, 3]$$$ (with a cost of $$$76$$$), and many others.

In the second example, the cost of the subset $$$[4, 6, 3, 1]$$$ is $$$90$$$.

Example input:
3
1 1 3 2 3 2
4 2
1 6
6 2
6 3
2 5

Example output:
3
2 4 5

Example input:
3
2 3 1 3 2 1
6 4
2 4
5 2
3 6
3 1

Example output:
4
1 3 4 6

Editorial:
Note that the cost function of a subset actually states the following: you are asked to choose the minimum lexicographic subset if the vertices are ordered in descending order. This can be shown by looking at the binary representations of the subset costs.
Intuitively, we want to implement the following process. Iterate over the vertices in descending order and check whether we have to take the current vertex in the subset, or we can skip it. If we can, we skip it; otherwise, we take it.
How to write this checking function? I think that it is easier to do this if we root the tree by a vertex that will definitely be in the answer. Finding such a vertex is easy — out of two vertices with the value $$$1$$$, at least one will definitely be in the answer. Iterate over it and take the best answer from the two options. We can compare the answers by their by binary representations.
In the rooted tree, where the root is always taken, it is easier to check connectivity. If a vertex is taken in the subset, then its parent must also be taken. Otherwise, the subset will definitely be disconnected.
A vertex must be taken in the subset if there is a value such that both vertices with this value are in its subtree. However, sometimes it happens that one of the two vertices with some value has already been prohibited from being taken. In this case, for this value, we need to check that only the non-prohibited vertex is in the subtree.
Let's maintain the state of each vertex:
• the vertex must be taken in the subset;
• the vertex must not be taken in the subset;
• it has not been determined whether to take the vertex or not.
Initially, we know that for each value, we must take the vertices that are on both paths from the vertices with this value to the root. So, on the path from their LCA (lowest common ancestor) to the root. If at least one such vertex is not taken, then that value will not appear in the subset.
A vertex can be skipped if its state is not determined. When we decide not to take a vertex, the following happens. The vertices in its subtree must also not be taken. And if for some vertex it is marked that it must not be taken in the subset, then another vertex with the same value must now be taken.
We will write two auxiliary functions.
The first function marks the state as "must take". So, it takes a vertex $$$v$$$ and jumps over the parents of vertex $$$v$$$ until it either reaches the root or an already marked vertex. In total, this function will make $$$O(n)$$$ iterations, as with each successful iteration of the loop, another vertex gets marked.
The second function marks the state as "must not take". That is, it takes a vertex $$$v$$$ and traverses the subtree of vertex $$$v$$$, marking all descendants as "must not take". I chose to implement this function using a breadth-first search. Again, we can stop the traversal when we see that a vertex is already marked as "must not take". In total, there will also be $$$O(n)$$$ iterations. When we mark a vertex, we call the first function from another vertex with its value.
Overall complexity: $$$O(n \log n)$$$ (where everything except LCA works in $$$O(n)$$$).