The World Of Dango
Time Limit: 2000ms
Memory Limit: 65536kb
DescriptionMaybe you have heard of the WORLD OF DANGO, an interesting game which is popular with girls. But this is a different story.
Long long ago, there was a magic kingdom, and many dangoes lives in some holes there. For the sake of simplicity, suppose there are N holes (1<=N<=2000), and ai dangoes live in hole i (0<=ai<=100000, 1<=i<=N). These holes are connected by N-1 undirected tubes. It is guaranteed that all holes are reachable from any one hole through these tubes.
There is a greedy cat named Tom. He’s so stupid that he mistakes dangoes as some kind of delicious food! So Tom decided to catch some dangoes and drive back home to cook a big meal. Tom’s car stays at hole S (0 <= S < N) initially. In order to have dinner on time, Tom must finish his work and go back to hole S in P minutes (exclusive), (1<=P<=8000), then drive away. Time would be counted from minute 0.
Note that moving from one hole to another hole would cost Tom 1 minute. If Tom wanna catch all the dangoes in the current hole, it would cost him another 2 minutes. Of course to save time, Tom has a choice to give up the dangoes in current hole and move to next hole.
Here comes the problem: can you tell Tom the maximum number of dangoes he can catch?
InputThere are several test cases. For each case:
First line contains three integers, N, S, P.
Second line contains N integers, a0, a1,…,aN-1, which means the number of dangoes in each hole.
Next N-1 lines, each line has two integer: a, b(0<=a, b<=N-1), meaning that there is a tube between hole a and b.
OutputA single line for each case, indicating the maximum number of dangoes Tom can catch.
1 0 1 2 1 0 2 2 1 0 100 2 4 0 6 5 5 5 100 0 1 1 3 0 2
0 2 2 100