CF1120D.Power Tree

You are given a rooted tree with $n$ vertices, the root of the tree is the vertex $1$. Each vertex has some non-negative price. A leaf of the tree is a non-root vertex that has degree $1$.

Arkady and Vasily play a strange game on the tree. The game consists of three stages. On the first stage Arkady buys some non-empty set of vertices of the tree. On the second stage Vasily puts some integers into all leaves of the tree. On the third stage Arkady can perform several (possibly none) operations of the following kind: choose some vertex $v$ he bought on the first stage and some integer $x$, and then add $x$ to all integers in the leaves in the subtree of $v$. The integer $x$ can be positive, negative of zero.

A leaf $a$ is in the subtree of a vertex $b$ if and only if the simple path between $a$ and the root goes through $b$.

Arkady's task is to make all integers in the leaves equal to zero. What is the minimum total cost $s$ he has to pay on the first stage to guarantee his own win independently of the integers Vasily puts on the second stage? Also, we ask you to find all such vertices that there is an optimal (i.e. with cost $s$) set of vertices containing this one such that Arkady can guarantee his own win buying this set on the first stage.

给你一棵包含 $n$ 个顶点的有根树，树的根为顶点 $1$。每个顶点具有某个非负价格。树的一个叶节点（leaf）是指非根节点且度数为 $1$ 的顶点。

阿尔卡季（Arkady）和瓦西里（Vasily）在该树上进行一场奇特的游戏。游戏分为三个阶段：

• 第一阶段，阿尔卡季购买树中某个非空的顶点集合；
• 第二阶段，瓦西里向树的所有叶节点中填入某些整数；
• 第三阶段，阿尔卡季可执行若干次（可能为零次）如下操作：选择一个他在第一阶段购买的顶点 $v$ 和某个整数 $x$，然后将 $x$ 加到以 $v$ 为根的子树中所有叶节点所含的整数上。其中 $x$ 可为正数、负数或零。

叶节点 $a$ 属于顶点 $b$ 的子树，当且仅当 $a$ 到根节点的简单路径经过 $b$。

阿尔卡季的目标是使所有叶节点中的整数都变为 $0$。问：为确保无论瓦西里在第二阶段填入何种整数，阿尔卡季都能获胜，他在第一阶段需支付的最小总费用 $s$ 是多少？此外，请找出所有满足如下条件的顶点：存在一个费用恰好为 $s$ 的最优顶点集合（即总费用为 $s$ 的集合），该集合包含此顶点，且阿尔卡季在第一阶段购买该集合即可保证获胜。

The first line contains a single integer $n$ ($2 \le n \le 200\,000$) — the number of vertices in the tree.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($0 \le c_i \le 10^9$), where $c_i$ is the price of the $i$-th vertex.

Each of the next $n - 1$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$), denoting an edge of the tree.

第一行包含一个整数 $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$），表示树中的一条边。

In the first line print two integers: the minimum possible cost $s$ Arkady has to pay to guarantee his own win, and the number of vertices $k$ that belong to at least one optimal set.

In the second line print $k$ distinct integers in increasing order the indices of the vertices that belong to at least one optimal set.

第一行输出两个整数：Arkady 为确保自己获胜所需支付的最小可能费用 $s$，以及属于至少一个最优集合的顶点个数 $k$。

第二行按升序输出 $k$ 个互不相同的整数，即属于至少一个最优集合的顶点的编号。

In the second example all sets of two vertices are optimal. So, each vertex is in at least one optimal set.

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