Maximum Weighted Path on a Tree

You are given a tree with $$n$$ nodes. Each node $$i$$ is assigned a weight $$a_i$$, where $$a_i \in {-1, 0, 1}$$. You need to choose a simple directed path $$P$$ (which can be empty) on the tree that satisfies the following conditions:

1. The path $$P$$ is a simple directed path (i.e. no vertex is repeated) and it can be empty.
2. If the path $$P$$ has vertices $$P_1, P_2, \cdots, P_{|P|}$$ then it must start at vertex $$1$$, i.e. $$P_1 = 1$$.
3. Define

$$f(P) = \sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}, $$

you must choose $$P$$ so that $$f(P)$$ is maximized. 4. Among all paths that maximize $$f(P)$$, choose the one with the lexicographically smallest sequence. The lexicographic order between two different paths $$P$$ and $$Q$$ is defined as follows:

• If there exists an index $$1 \le i \le \min(|P|,|Q|)$$ such that $$P_1=Q_1, \ldots, P_{i-1}=Q_{i-1}$$ and $$P_i<Q_i$$, then $$P$$ is lexicographically smaller than $$Q$$.
• If one path is a prefix of the other, the shorter path is considered lexicographically smaller.

Your task is to output the vertices of the chosen path in order. Note that although the path is described as "possibly empty", the condition $$P_1 = 1$$ forces at least one vertex in the solution.

inputFormat

The input begins with an integer $$n$$, the number of nodes in the tree. The second line contains $$n$$ integers $$a_1, a_2, \ldots, a_n$$ (each of which is -1, 0, or 1). The next $$n-1$$ lines each contain two integers $$u$$ and $$v$$, indicating that there is an edge between nodes $$u$$ and $$v$$.

outputFormat

Output the vertices of the selected path in order, separated by spaces.

sample

1
1

1