547. Divide The Kingdom
Time limit per test: 1
Memory limit: 262144
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:
- his subset of cities is connected (i.e. for every pair of his cities A and B, there is always a path from A to B that passes only through the King's cities),
- he does not share any cities with the Queen,
- none of his cities are directly connected by a road to any of the Queen's cities,
- if you consider distances between all pairs of his cities, the length of the longest path must be equal to D1,
- if you consider all pairs of his cities which are located at distance D1 from each other and then calculate the number of different cities within all these pairs, this number must not exceed C1 (formally, if his subset contains the only city then the number of such pairs equals 0).
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
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
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
(0 ≤ D1
-1, 1 ≤ C1
). The third line contains n
integer costs pi
(1 ≤ pi
≤ 1000). Each of the next n
-1 lines contains two integer numbers aj
(1 ≤ aj
), meaning that the j
-th road connects cities aj
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.
4 2 0 1
5 2 5 2 5 5 5 5 5 2
2 4 10
1 2 1 2
9 9 9 9
In the first test case, the optimal solution is as follows:
- In the first place, city 10 is destroyed and the kingdom falls apart into two parts. The smallest part contains an isolated city 9, and it already satisfies the Queen's requirements.
- The second remaining part is a little bit too large for the King. The maximum distance between pairs of cities (2,5), (4,5), (6,5) is 4, exactly as the King wants. But the number of these cities [2, 4, 5, 6] is 4, while the King's desire is to have not more than 2. So, it's additionally required to destroy cities 2 and 4.
- Overall, destroying cities [2, 4, 10] costs 6 burles. It's an optimal solution from the cost perspective.
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.