CF1120D Power Tree

给定一棵有 $n$ 个顶点的有根树，树的根为顶点 $1$。每个顶点都有一个非负的价格。树的叶子是指度为 $1$ 且不是根的顶点。 Arkady 和 Vasily 在树上玩一个奇怪的游戏。游戏分为三个阶段。第一阶段，Arkady 购买树上的一些非空顶点集合。第二阶段，Vasily 给所有叶子节点赋一些整数。第三阶段，Arkady 可以进行若干次（也可以不进行）如下操作：选择他在第一阶段购买的某个顶点 $v$ 和某个整数 $x$，然后将 $x$ 加到 $v$ 的子树中所有叶子的整数上。整数 $x$ 可以是正数、负数或零。 如果一条从叶子 $a$ 到根的简单路径经过顶点 $b$，则称叶子 $a$ 在顶点 $b$ 的子树中。 Arkady 的目标是让所有叶子上的整数都变为零。无论 Vasily 在第二阶段如何赋值，Arkady 都要保证自己能够达成目标。请你求出 Arkady 在第一阶段至少需要支付的总费用 $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$ 个不同的整数，按升序排列，表示属于至少一个最优集合的顶点编号。

在第二个样例中，所有包含两个顶点的集合都是最优的。因此，每个顶点都至少属于一个最优集合。 由 ChatGPT 4.1 翻译