luogu#P8977. 「DTOI-4」行走

    ID: 12962 远端评测题 500ms 128MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>数学贪心2023洛谷原创O2优化深度优先搜索,DFS

「DTOI-4」行走

题目背景

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

题目描述

小 L 有一棵 nn 个点的树,树上点有点权,其中第 ii 个点权值为 aia_i

他不喜欢奇奇怪怪的权值,于是他保证 aia_i 一定是 1,0,1-1, 0, 1 之一。

他认为在树上行走是有趣的,于是他想要在这棵树上走出一条路径 PP,其需要满足以下条件:

  • PP 是一条可以为空简单有向路径
  • PP 中依次经过的点为 P1,P2,,PPP_1, P_2, \cdots, P_{|P|},则你求出的 PP 需要满足 P1=1P_1 = 1
  • 设 $f(P) = \displaystyle\sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}$,则你求出的 PP 需要满足 f(P)f(P) 最大。
  • f(P)f(P) 最大的前提下,你求出的 PP 还需要满足 PP 的字典序最小。

请你求出符合上述条件的路径 PP


关于本题中字典序的定义:

设有两条待比较的路径 PQP \neq Q

  • 若存在 1imin(P,Q)1 \leq i \leq \min(|P|, |Q|),使得 1j<i,Pj=Qj\forall 1 \leq j < i, P_j = Q_jPi<QiP_i < Q_i,则我们称 PP 的字典序小于 QQ
  • 若存在 1imin(P,Q)1 \leq i \leq \min(|P|, |Q|),使得 1j<i,Pj=Qj\forall 1 \leq j < i, P_j = Q_jPi>QiP_i > Q_i,则我们称 PP 的字典序大于 QQ
  • 1imin(P,Q),Pi=Qi\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_iP<Q|P| < |Q|,则我们称 PP 的字典序小于 QQ
  • 1imin(P,Q),Pi=Qi\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_iP>Q|P| > |Q|,则我们称 PP 的字典序大于 QQ

输入格式

第一行,一个整数 nn

第二行,nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n

接下来 n1n - 1 行,每行两个整数 u,vu, v,表示树上的一条边。

输出格式

一行,P|P| 个整数,表示你求出的路径 PP 中依次经过的点。

特别的,若 PP 为空路径,请不要进行任何输出操作。

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

提示

样例 #1 解释

P=[1,2,4]P = [1, 2, 4]f(P)=1+0+14=54f(P) = 1 + 0 + \frac{1}{4} = \frac{5}{4}。可以证明不存在更优的 PP

数据范围

Subtask\textbf{Subtask} nn aia_i 依赖 分值
11 1n501 \leq n \leq 50 无特殊限制 10pts10 \operatorname{pts}
22 1n5001 \leq n \leq 500 同上 11
33 1n5×1031 \leq n \leq 5 \times 10^3 1,21, 2
44 1n1051 \leq n \leq 10^5 131 \sim 3 20pts20 \operatorname{pts}
55 无特殊限制 ai{1,1}a_i \in \{-1, 1\}
66 同上 无特殊限制 151 \sim 5 30pts30 \operatorname{pts}

对于 100%100\% 的数据,1n5×1051 \leq n \leq 5 \times 10^5ai{1,0,1}a_i \in \{-1, 0, 1\}1u,vn1 \leq u, v \leq n,保证给出的边可以构成一棵无根树