P12895 [POI 2019/2020 R2] 假期 Wakacje Bajtazara

翻译来自于 [LibreOJ](https://loj.ac/p/4844)。

**题目译自 [XXVII Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi27-2/dashboard/) [Wakacje Bajtazara](https://szkopul.edu.pl/problemset/problem/pXcijJbDyC_jRAjkoxBH9sCO/statement/)** 众所周知，Bajtazar 是一个非常忙碌的人，他从不畏惧字节王国中的任何生活挑战。不过，他终于决定给自己放个假，于是前往比特王国度假。比特王国中有 $n$ 座城市，通过 $n-1$ 条双向道路连接，确保任意两座城市之间都可以通行。Bajtazar 不想连续两天待在同一座城市，但他也不喜欢长途跋涉，所以每天晚上他计划只通过一条道路前往邻近城市。他为每座城市设定了吸引力系数，用来衡量游览这座城市的愉悦程度。当然，他希望度过一个尽可能愉快的假期。 然而，Bajtazar 就是 Bajtazar，他总是喜欢将愉快与实用相结合。这次假期也不例外，他打算利用假期时间开始撰写回忆录。具体来说，他计划在假期中每隔一天游览城市，其余日子用来写作。 他希望规划一个长度为 $2k-1$ 天的假期，其中在 $k$ 个奇数日游览城市，在 $k-1$ 个偶数日写作回忆录。游览过的城市的吸引力系数总和必须尽可能大，同时他不想重复游览同一座城市。不过，在写作的日子，他并不介意待在之前已经去过的城市。请你帮助他规划一个最愉快的假期。

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 1000000)$，表示比特王国中的城市数量。城市编号从 $1$ 到 $n$。 第二行包含 $n$ 个整数 $w_{1}, w_{2}, \ldots, w_{n}$ $(1 \leq w_{i} \leq 1000000)$，用单个空格分隔，$w_{i}$ 表示编号为 $i$ 的城市的吸引力系数。 接下来的 $n-1$ 行描述比特王国的道路，每行包含两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq n)$，用单个空格分隔，表示编号为 $a_{i}$ 和 $b_{i}$ 的城市之间有一条双向道路。

你的程序应输出三行内容： 第一行包含一个整数 $W$，表示 Bajtazar 假期中能获得的最大吸引力系数总和。 第二行包含一个整数 $k$，表示 Bajtazar 在假期中游览的城市数量。 第三行包含 $2k-1$ 个整数，用单个空格分隔，表示 Bajtazar 在假期各天所在的城市编号。如果存在多种最大 $W$ 的方案，你的程序可以输出任意一种。

**样例 1 解释** 下图展示了比特王国的道路网络示意图。Bajtazar 将游览城市 $3$、$1$、$4$ 和 $7$，这些城市的吸引力系数总和为 $5+3+4+1=13$。  **附加样例** 1. 该样例满足四座城市连成一条路径，每座城市的吸引力系数均为 $1$。 2. 该样例满足七座城市构成一棵满二叉树，每座城市的吸引力系数等于其所在深度（根节点深度为 $1$）。 3. 该样例满足一千座城市，每座城市（除了城市 $1$）都与城市 $1$ 直接相连，每座城市的吸引力系数均为 $1$。 4. 该样例满足一百万座城市连成一条路径，每座城市的吸引力系数为 $1$、$2$ 或 $3$。 详细子任务附加限制及分值如下表所示。 如果你的程序正确输出了第一行（即 $W$），但其他行不正确，可以获得该测试点 $40\%$ 的分数。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 1000$，所有 $w_{i}=1$ | $20$ | | $2$ | $n \leq 1000$ | $10$ | | $3$ | 所有 $w_{i}=1$ | $40$ | | $4$ | 无附加限制 | $30$ |