547. Divide The Kingdom

Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Once upon a time, long, long ago there lived a King and a Queen who ruled over a distant kingdom called Berland.

Their kingdom contained n cities connected by n-1 bi-directional roads. The roads were constructed in such a way that Berland citizens were able to reach any city from any other city by walking along these roads.

One day the King and the Queen decided that they want to break up the relationship. Yes, it's not common when it comes to a royal marriage, but it's something they decided to do and we have to respect their decision. Of course, now they want to divide the kingdom and start living separately from each other. Each of them wants to take a part of the existing kingdom. Moreover, they want their own parts to be very special, so their requirements are quite complicated.

So, the King wants to pick a nonempty subset of cities from the existing kingdom. He will be satisfied only if all following conditions are met:

The Queen wants to pick a nonempty subset of cities as well. Her requirements are essentially the same as the King's ones, with the exception of the numbers she has in mind — D2 and C2 respectively. Obviously, she is not allowed to take cities which have been already taken by the King, her subset of cities should be connected and none of her cities should be adjacent to the King's cities.

Now, what about the remaining cities, the ones that will not belong to either the King or the Queen after the kingdom is divided? The answer is simple — they have to be destroyed along with all roads coming into them, and all people should be evacuated from these cities. Destroying the i-th city will cost pi burles.

Can you help the King and the Queen with the separation? You task is to figure out whether it's possible to perform separation of the kingdom according to the rules described above. If the separation is possible, you have to find a way with the minimum possible cost of cities that will be destroyed.

The first line of the input contains a positive integer n (3 ≤ n ≤ 200) — the number of cities in the kingdom. The second line contains integers D1, C1, D2, C2 (0 ≤ D1, D2n-1, 1 ≤ C1, C2n). The third line contains n integer costs pi (1 ≤ pi ≤ 1000). Each of the next n-1 lines contains two integer numbers aj and bj (1 ≤ aj, bjn), meaning that the j-th road connects cities aj and bj.

If there is no solution, write "
" (without the quotes) in a single output line.

Otherwise, output the total cost of destroyed cities in the first line, and print the numbers of destroyed cities in the increasing order in the second line. If there are multiple solutions, you may print any of them.

sample input
sample output
4 2 0 1
5 2 5 2 5 5 5 5 5 2
1 4
6 1
1 2
7 1
3 7
10 7
9 10
7 8
8 5
2 4 10

sample input
sample output
1 2 1 2
9 9 9 9
1 2
2 3
3 4

In the first test case, the optimal solution is as follows:

In the second test case there is no solution. Obviously, at least one city should be deleted from the kingdom, while D1=1 requires two adjacent cities, and D2=1 requires another two adjacent cities. So, we could possibly achieve the required outcome with 5 cities in a line, but not with 4.

Online Contester Team © 2002 - 2010. All rights reserved.