The bravest man
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 207
Solved: 62
- Description
- Being the bravest man on the earth, you decide to conquer the evil planet X. On arrival of X, you find that the map of this planet is very special. There are N islands on it, which are connected by some bridges and form a shape of a tree. And they are numbered from 1 to N. Now there are some guards on those islands. The number of the guards on every island is not more than M.
You have brought a special kind of bomb. When the bomb is set off on one island, one of the guards on this island, as well as every island that is connected directly with it, will die.
To prove that you are not only the bravest man on the earth, but also the smartest one, you want to end this battle at a smallest number of bombs. - Input
- There are multi cases.
For each case, there are several lines. The first line contains a single integer N. The next line contains N numbers, the kth number specifies the number of guards on the kth island. In the following N-1 lines, every line contains two integers i and j, specifies that there is a bridge between island i and island j.
All the integers in the input is not greater than 50.
There is a blank line between the consective cases. - Output
- For each case, just output a single line contains the smallest number of bombs you must use.
- sample input
-
3 5 8 8 1 2 3 1 8 2 2 6 10 8 8 7 8 2 3 6 3 8 5 6 8 4 7 1 5 4 5
- sample output
-
8 18
- hint
- In the first sample case, you can set off 8 bombs on the island 1. In the second sample case, you can set off 2 bombs on the island 3, 7 bombs on the island 4, 3 bombs on the island 5, 4 bombs on the island 6 and 2 bombs on the island 8.
- source
- Du p