题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXVII Olimpiada Informatyczna – II etap Wakacje Bajtazara

众所周知，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$ 的方案，你的程序可以输出任意一种。

8
3 8 5 4 1 2 1 1
1 2
2 3
2 4
5 4
4 6
7 6
8 7

13
4
3 2 1 2 4 6 7

提示

样例 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\%$ 的分数。