Power Tree
Contest: Technocup 2019 - Final
Difficulty rating: 2500
Tags: dfs and similar, dp, graphs, trees

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
5
5 1 3 2 1
1 2
2 3
2 4
1 5

Example output:
4 3
2 4 5

Example input:
3
1 1 1
1 2
1 3

Example output:
2 3
1 2 3

Editorial:
One can see that the problem doesn't change if we want to be able to obtain any possible combination of numbers in leaves from the all-zero combination.
Solution 1. Let $$$v_1$$$, $$$v_2$$$, ..., $$$v_l$$$ be the indices of all leaves in the order of any Euler tour. Let $$$a_i$$$ be the number written in $$$v_i$$$. We say that $$$v_0 = v_{l+1} = 0$$$. Denote the difference $$$a_{i + 1} - a_i$$$ by $$$d_i$$$. We want to be able to obtain an arbitrary sequence $$$d_0$$$, ..., $$$d_l$$$ with zero sum.
Imagine that we bought a vertex $$$u$$$ whose subtree contains exactly leaves from $$$v_i$$$ to $$$v_j$$$. Applying the operation to this vertex with number $$$x$$$ means increasing $$$d_{i-1}$$$ by $$$x$$$ and decreasing $$$d_j$$$ by $$$x$$$ without affecting all other differences.
Let's build new graph with vertices from $$$0$$$ to $$$l$$$. Each such vertex $$$u$$$ represents an edge connecting vertices $$$(i - 1)$$$ and $$$j$$$ with weight $$$c_u$$$. To be able to get every possible sequence with zero sum it's needed and sufficient for the graph with picked edges be connected. Now we want to know what is the weight of a minimal spanning tree and which edges can be in it. Both can be found by, for example, Kruskal's algorithm.
Solution 2. We say that a vertex $$$u$$$ covers a leaf $$$v$$$ if it's in $$$u$$$'s subtree.
One can see that we can buy a set of vertices iff for each vertex $$$u$$$ there is at most one leaf in its subtree which is not covered by any of bought vertices from the subtree. Indeed, if there are at least two such leaves then the difference between their values never change. On the other hand, if this holds, we can set the required values in the bought vertices in the order of increasing depth, performing the needed operation each time we are in vertex whose subtree contains a leaf which is not covered by any bought vertex in the subtree except the one we consider.
So we calculate $$$ans[v][k]$$$ where $$$0\le k\le 1$$$ where this value means the minimal possible cost where in the subtree of $$$v$$$ there are $$$k$$$ not covered leaves. It can be shown that these values are enough to calculate the answer.