题目描述

众所周知，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 5 4 1 2 1
1 2
2 3
2 4
5 4
4 6
7 6
8 7

13
4
3 2 1 2 4 6 7

样例 2

见附加文件下 [wak1.in](file:wak1.in) 和 [wak1.out](file:wak1.out)。

该样例满足四座城市连成一条路径，每座城市的吸引力系数均为 $1$。

样例 3

见附加文件下 [wak2.in](file:wak2.in) 和 [wak2.out](file:wak2.out)。

该样例满足七座城市构成一棵满二叉树，每座城市的吸引力系数等于其所在深度（根节点深度为 $1$）。

样例 4

见附加文件下 [wak3.in](file:wak3.in) 和 [wak3.out](file:wak3.out)。

该样例满足一千座城市，每座城市（除了城市 $1$）都与城市 $1$ 直接相连，每座城市的吸引力系数均为 $1$。

样例 5

见附加文件下 [wak4.in](file:wak4.in) 和 [wak4.out](file:wak4.out)。

该样例满足一百万座城市连成一条路径，每座城市的吸引力系数为 $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$