给你一棵有 $$$n$$$ 个顶点的有根树,树的根是顶点 $$$1$$$。每个顶点都有一些非负价格。树的叶子是度为 $$$1$$$ 的非根顶点。
阿尔卡迪和瓦西里在树上玩着奇怪的游戏。比赛由三个阶段组成。在第一阶段,Arkady 购买了树的一些非空顶点集。在第二阶段,瓦西里将一些整数放入树的所有叶子中。在第三阶段,Arkady 可以执行以下几种(可能没有)操作:选择他在第一阶段购买的一些顶点 $$$v$$$ 和一些整数 $$$x$$$,然后将 $$$x$$$ 添加到 $$$v$$$ 子树中叶子中的所有整数。整数 $$$x$$$ 可以是正数,也可以是负数零。
当且仅当 $$$a$$$ 和根之间的简单路径经过 $$$b$$$ 时,叶子 $$$a$$$ 位于顶点 $$$b$$$ 的子树中。
Arkady 的任务是使叶子中的所有整数都等于 0。无论瓦西里在第二阶段输入的整数如何,他在第一阶段必须支付的最小总成本 $$$s$$$ 才能保证自己获胜?另外,我们要求您找到所有这样的顶点,其中存在包含该顶点的最佳(即成本 $$$s$$$)顶点集,以便 Arkady 可以保证自己在第一阶段购买该集合时获胜。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200\,000$$$) — 树中的顶点数。
第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \le c_i \le 10^9$$$),其中 $$$c_i$$$ 是第 $$$i$$$ 个顶点的价格。
接下来的 $$$n - 1$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$),表示树的一条边。
输出
在第一行中打印两个整数:Arkady 为保证自己获胜而必须支付的最小可能成本 $$$s$$$,以及属于至少一个最优集的顶点数 $$$k$$$。
在第二行中,按升序打印 $$$k$$$ 个不同的整数,这些整数属于至少一个最优集的顶点索引。
示例
输入 #1
5 5 1 3 2 1 1 2 2 3 2 4 1 5
输出 #1
4 3 2 4 5
输入 #2
3 1 1 1 1 2 1 3
输出 #2
2 3 1 2 3
注意
在第二个示例中,所有两个顶点的集合都是最优的。因此,每个顶点至少位于一个最佳集合中。