「DTOI-4」行走

小 L 感到无聊，于是希望在树上行走。

小 L 有一棵 $n$ 个点的树，树上点有点权，其中第 $i$ 个点权值为 $a_i$。 他不喜欢奇奇怪怪的权值，于是他保证 $a_i$ 一定是 $-1, 0, 1$ 之一。 他认为在树上行走是有趣的，于是他想要在这棵树上走出一条路径 $P$，其需要满足以下条件： - $P$ 是一条**可以为空**的**简单有向路径**。 - 设 $P$ 中依次经过的点为 $P_1, P_2, \cdots, P_{|P|}$，则你求出的 $P$ 需要满足 $P_1 = 1$。 - 设 $f(P) = \displaystyle\sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}$，则你求出的 $P$ 需要满足 $f(P)$ 最大。 - 在 $f(P)$ 最大的前提下，你求出的 $P$ 还需要满足 $P$ 的字典序最小。 请你求出符合上述条件的路径 $P$。 ------------ 关于本题中字典序的定义： 设有两条待比较的路径 $P \neq Q$。 - 若存在 $1 \leq i \leq \min(|P|, |Q|)$，使得 $\forall 1 \leq j < i, P_j = Q_j$ 且 $P_i < Q_i$，则我们称 $P$ 的字典序小于 $Q$。 - 若存在 $1 \leq i \leq \min(|P|, |Q|)$，使得 $\forall 1 \leq j < i, P_j = Q_j$ 且 $P_i > Q_i$，则我们称 $P$ 的字典序大于 $Q$。 - 若 $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ 且 $|P| < |Q|$，则我们称 $P$ 的字典序小于 $Q$。 - 若 $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ 且 $|P| > |Q|$，则我们称 $P$ 的字典序大于 $Q$。

第一行，一个整数 $n$； 第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$； 接下来 $n - 1$ 行，每行两个整数 $u, v$，表示树上的一条边。

一行，$|P|$ 个整数，表示你求出的路径 $P$ 中依次经过的点。 **特别的，若 $P$ 为空路径，请不要进行任何输出操作。**

5
1 0 -1 1 -1
1 2
2 3
2 4
1 5

1 2 4

#### 样例 #1 解释  $P = [1, 2, 4]$ 时 $f(P) = 1 + 0 + \frac{1}{4} = \frac{5}{4}$。可以证明不存在更优的 $P$。 #### 数据范围 | $\textbf{Subtask}$ | $n$ | $a_i$ | 依赖 | 分值 | | :------: | :------: | :------: | :------: | :------: | | $1$ | $1 \leq n \leq 50$ | 无特殊限制 | 无 | $10 \operatorname{pts}$ | | $2$ | $1 \leq n \leq 500$ | 同上 | $1$ | $10 \operatorname{pts}$ | | $3$ | $1 \leq n \leq 5 \times 10^3$ | 同上 | $1, 2$ | $10 \operatorname{pts}$ | | $4$ | $1 \leq n \leq 10^5$ | 同上 | $1 \sim 3$ | $20 \operatorname{pts}$ | | $5$ | 无特殊限制 | $a_i \in \{-1, 1\}$ | 无 | $20 \operatorname{pts}$ | | $6$ | 同上 | 无特殊限制 | $1 \sim 5$ | $30 \operatorname{pts}$ | 对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$a_i \in \{-1, 0, 1\}$，$1 \leq u, v \leq n$，保证给出的边可以构成一棵**无根树**。