P8977 "DTOI-4" Walking.

Xiao L feels bored, so he wants to walk on a tree.

Xiao L has a tree with $n$ nodes. Each node has a weight, and the weight of node $i$ is $a_i$. He does not like strange weights, so he guarantees that $a_i$ must be one of $-1, 0, 1$. He thinks walking on a tree is interesting, so he wants to find a path $P$ on this tree that satisfies the following conditions: - $P$ is a **simple directed path** that **can be empty**. - Let the nodes visited by $P$ in order be $P_1, P_2, \cdots, P_{|P|}$. The path you find must satisfy $P_1 = 1$. - Let $f(P) = \displaystyle\sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}$. The path you find must maximize $f(P)$. - Under the condition that $f(P)$ is maximized, the path you find must also have the smallest lexicographical order. Please find a path $P$ that satisfies the conditions above. ------------ Definition of lexicographical order in this problem: Given two paths to compare $P \neq Q$. - If there exists $1 \leq i \leq \min(|P|, |Q|)$ such that $\forall 1 \leq j < i, P_j = Q_j$ and $P_i < Q_i$, then we say that $P$ is lexicographically smaller than $Q$. - If there exists $1 \leq i \leq \min(|P|, |Q|)$ such that $\forall 1 \leq j < i, P_j = Q_j$ and $P_i > Q_i$, then we say that $P$ is lexicographically larger than $Q$. - If $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ and $|P| < |Q|$, then we say that $P$ is lexicographically smaller than $Q$. - If $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ and $|P| > |Q|$, then we say that $P$ is lexicographically larger than $Q$.

The first line contains an integer $n$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$. The next $n - 1$ lines each contain two integers $u, v$, representing an edge in the tree.

Output one line with $|P|$ integers, representing the nodes visited by the path $P$ in order. **In particular, if $P$ is an empty path, do not output anything.**

#### Sample #1 Explanation  When $P = [1, 2, 4]$, we have $f(P) = 1 + 0 + \frac{1}{4} = \frac{5}{4}$. It can be proven that there is no better $P$. #### Constraints | $\textbf{Subtask}$ | $n$ | $a_i$ | Dependencies | Score | | :------: | :------: | :------: | :------: | :------: | | $1$ | $1 \leq n \leq 50$ | No special restrictions | None | $10 \operatorname{pts}$ | | $2$ | $1 \leq n \leq 500$ | Same as above | $1$ | $10 \operatorname{pts}$ | | $3$ | $1 \leq n \leq 5 \times 10^3$ | Same as above | $1, 2$ | $10 \operatorname{pts}$ | | $4$ | $1 \leq n \leq 10^5$ | Same as above | $1 \sim 3$ | $20 \operatorname{pts}$ | | $5$ | No special restrictions | $a_i \in \{-1, 1\}$ | None | $20 \operatorname{pts}$ | | $6$ | Same as above | No special restrictions | $1 \sim 5$ | $30 \operatorname{pts}$ | For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $a_i \in \{-1, 0, 1\}$, $1 \leq u, v \leq n$. It is guaranteed that the given edges form an **unrooted tree**. Translated by ChatGPT 5