题目背景
小 L 感到无聊,于是希望在树上行走。
题目描述
小 L 有一棵 n 个点的树,树上点有点权,其中第 i 个点权值为 ai。
他不喜欢奇奇怪怪的权值,于是他保证 ai 一定是 −1,0,1 之一。
他认为在树上行走是有趣的,于是他想要在这棵树上走出一条路径 P,其需要满足以下条件:
- P 是一条可以为空的简单有向路径。
- 设 P 中依次经过的点为 P1,P2,⋯,P∣P∣,则你求出的 P 需要满足 P1=1。
- 设 $f(P) = \displaystyle\sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}$,则你求出的 P 需要满足 f(P) 最大。
- 在 f(P) 最大的前提下,你求出的 P 还需要满足 P 的字典序最小。
请你求出符合上述条件的路径 P。
关于本题中字典序的定义:
设有两条待比较的路径 P=Q。
- 若存在 1≤i≤min(∣P∣,∣Q∣),使得 ∀1≤j<i,Pj=Qj 且 Pi<Qi,则我们称 P 的字典序小于 Q。
- 若存在 1≤i≤min(∣P∣,∣Q∣),使得 ∀1≤j<i,Pj=Qj 且 Pi>Qi,则我们称 P 的字典序大于 Q。
- 若 ∀1≤i≤min(∣P∣,∣Q∣),Pi=Qi 且 ∣P∣<∣Q∣,则我们称 P 的字典序小于 Q。
- 若 ∀1≤i≤min(∣P∣,∣Q∣),Pi=Qi 且 ∣P∣>∣Q∣,则我们称 P 的字典序大于 Q。
输入格式
第一行,一个整数 n;
第二行,n 个整数 a1,a2,⋯,an;
接下来 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+41=45。可以证明不存在更优的 P。
数据范围
Subtask |
n |
ai |
依赖 |
分值 |
1 |
1≤n≤50 |
无特殊限制 |
无 |
10pts |
2 |
1≤n≤500 |
同上 |
1 |
3 |
1≤n≤5×103 |
1,2 |
4 |
1≤n≤105 |
1∼3 |
20pts |
5 |
无特殊限制 |
ai∈{−1,1} |
无 |
6 |
同上 |
无特殊限制 |
1∼5 |
30pts |
对于 100% 的数据,1≤n≤5×105,ai∈{−1,0,1},1≤u,v≤n,保证给出的边可以构成一棵无根树。