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:
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.
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.
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.
31 1 3 2 3 24 21 66 26 32 5
3 2 4 5
32 3 1 3 2 16 42 45 23 63 1
4 1 3 4 6
65 2 3 4 6 4 2 5 6 1 1 310 82 1012 74 105 96 21 93 412 611 54 5
6 2 3 4 5 8 10
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$$$.
Name |
---|