[Login|Register]
Problems

Status

Rank

Problem 1157
The World Of Dango
Time Limit: 2000ms
Memory Limit: 65536kb
Description
Maybe 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?

Input
There 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.

Output
A single line for each case, indicating the maximum number of dangoes Tom can catch.
Sample Input
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
Sample Output
0
2
2
100
Source
lianjx@ustc
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 2.8ms with 1 query(s).