{"problem":{"name":"「DTOI-4」行走","description":{"content":"小 L 有一棵 $n$ 个点的树，树上点有点权，其中第 $i$ 个点权值为 $a_i$。 他不喜欢奇奇怪怪的权值，于是他保证 $a_i$ 一定是 $-1, 0, 1$ 之一。 他认为在树上行走是有趣的，于是他想要在这棵树上走出一条路径 $P$，其需要满足以下条件： - $P$ 是一条**可以为空**的**简单有向路径**。 - 设 $P$ 中依次经过的点为 $P_1, P_2, \\cdots","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8977"},"statements":[{"statement_type":"Markdown","content":"小 L 有一棵 $n$ 个点的树，树上点有点权，其中第 $i$ 个点权值为 $a_i$。\n\n他不喜欢奇奇怪怪的权值，于是他保证 $a_i$ 一定是 $-1, 0, 1$ 之一。\n\n他认为在树上行走是有趣的，于是他想要在这棵树上走出一条路径 $P$，其需要满足以下条件：\n\n- $P$ 是一条**可以为空**的**简单有向路径**。\n- 设 $P$ 中依次经过的点为 $P_1, P_2, \\cdots, P_{|P|}$，则你求出的 $P$ 需要满足 $P_1 = 1$。\n- 设 $f(P) = \\displaystyle\\sum_{i = 1}^{|P|} \\frac{a_{P_i}}{2^{i - 1}}$，则你求出的 $P$ 需要满足 $f(P)$ 最大。\n- 在 $f(P)$ 最大的前提下，你求出的 $P$ 还需要满足 $P$ 的字典序最小。\n\n请你求出符合上述条件的路径 $P$。 \n\n------------\n\n关于本题中字典序的定义：\n\n设有两条待比较的路径 $P \\neq Q$。\n\n- 若存在 $1 \\leq i \\leq \\min(|P|, |Q|)$，使得 $\\forall 1 \\leq j < i, P_j = Q_j$ 且 $P_i < Q_i$，则我们称 $P$ 的字典序小于 $Q$。\n- 若存在 $1 \\leq i \\leq \\min(|P|, |Q|)$，使得 $\\forall 1 \\leq j < i, P_j = Q_j$ 且 $P_i > Q_i$，则我们称 $P$ 的字典序大于 $Q$。\n- 若 $\\forall 1 \\leq i \\leq \\min(|P|, |Q|), P_i = Q_i$ 且 $|P| < |Q|$，则我们称 $P$ 的字典序小于 $Q$。\n- 若 $\\forall 1 \\leq i \\leq \\min(|P|, |Q|), P_i = Q_i$ 且 $|P| > |Q|$，则我们称 $P$ 的字典序大于 $Q$。\n\n## Input\n\n第一行，一个整数 $n$；\n\n第二行，$n$ 个整数 $a_1, a_2, \\cdots, a_n$；\n\n接下来 $n - 1$ 行，每行两个整数 $u, v$，表示树上的一条边。\n\n## Output\n\n一行，$|P|$ 个整数，表示你求出的路径 $P$ 中依次经过的点。\n\n**特别的，若 $P$ 为空路径，请不要进行任何输出操作。**\n\n[samples]\n\n## Background\n\n小 L 感到无聊，于是希望在树上行走。\n\n## Note\n\n#### 样例 #1 解释\n![](https://cdn.luogu.com.cn/upload/image_hosting/c7n2n6i0.png)\n\n$P = [1, 2, 4]$ 时 $f(P) = 1 + 0 + \\frac{1}{4} = \\frac{5}{4}$。可以证明不存在更优的 $P$。\n#### 数据范围\n| $\\textbf{Subtask}$ | $n$ | $a_i$ | 依赖 | 分值 |\n| :------: | :------: | :------: | :------: | :------: |\n| $1$ | $1 \\leq n \\leq 50$ | 无特殊限制 | 无 | $10 \\operatorname{pts}$ |\n| $2$ | $1 \\leq n \\leq 500$ | 同上 | $1$ | $10 \\operatorname{pts}$ |\n| $3$ | $1 \\leq n \\leq 5 \\times 10^3$ | 同上 | $1, 2$ | $10 \\operatorname{pts}$ |\n| $4$ | $1 \\leq n \\leq 10^5$ | 同上 | $1 \\sim 3$ | $20 \\operatorname{pts}$ |\n| $5$ | 无特殊限制 | $a_i \\in \\{-1, 1\\}$ | 无 | $20 \\operatorname{pts}$ |\n| $6$ | 同上 | 无特殊限制 | $1 \\sim 5$ | $30 \\operatorname{pts}$ |\n\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 5 \\times 10^5$，$a_i \\in \\{-1, 0, 1\\}$，$1 \\leq u, v \\leq n$，保证给出的边可以构成一棵**无根树**。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8977","tags":["数学","贪心","2023","洛谷原创","O2优化","深度优先搜索 DFS"],"sample_group":[["5\n1 0 -1 1 -1\n1 2\n2 3\n2 4\n1 5","1 2 4"]],"created_at":"2026-03-03 11:09:25"}}