Maximum Independent Set in a Tree

You are given a tree whose vertices have weights. An independent set is a set of vertices in which no two vertices are directly connected by an edge. The size of an independent set is the sum of the weights of its vertices. The empty set has size 0.

Find an independent set of maximum total weight in the given tree.

The first line contains the number of vertices n. n is a positive integer not greater than 10,000. The vertices are numbered from 1 to n.

The second line contains n integers w_1, w_2, ..., w_n. Here, w_i is the weight of vertex i, and every weight is a positive integer not greater than 10,000.

Each of the next n-1 lines contains one edge of the tree, given as the two endpoint vertex numbers. All integers in the input are separated by a single space.

Print the maximum total weight of an independent set on the first line.

On the second line, print the vertices in that independent set in increasing order. If there is more than one maximum independent set, you may print any one of them.