Rikka with Game

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. But today Rikka doesn't want to do math tasks, so they begin to play some games:

Long long ago, There is a continent which has $n$ citis and $n-1$ roads on it. Each city is connected to others directly or indirectly.

Now you want to build your own kingdom and make city 1 be the capital. Then you will cut off all the roads which connects a city which belong to your country and a city outside your country. Your country must satisfy the following rules:

1.City 1 must belong to your country.

2.Each pair of cities in your country can get to each other by the roads which haven't been cut off.

After cutting off the roads, actually, the continent has been cut to many unicom blocks. And then each unicom block develops into an independent state. To preserve the peace, you need to choose at most $k$ other counties (can't be your own country) and establish diplomatic relations with them.

Each city have a prosperous value $w_i$ and the prosperous value of each country is equal to the sum of the prosperous value of the citis in it. And the stable value of your country is eaual the prosperous value of your own country plus $a \times$ the sum of the prosperous value of the countrie which have diplomatic relations with you.

Now, you need to maximal the stable value.

It is too difficult for Rikka. Can you help her?

There are no more than 1000 testcases and there are no more than 3 testcase meet $n,k \geq 100$.

For each testcase, the first line contains three integers $n,a,k(1 \leq n \leq 10^5, -10^3 \leq a \leq 10^3, 0 \leq k \leq 500)$.

The second line contains $n$ integers $w_i(-10^9 \leq w_i \leq 10^9)$

Then $n-1$ lines follow. Each line contains two numbers $u,v(1 \leq u,v \leq n)$ , which means there is an edge between $u$ and $v$.

For each testcase, print a single number -- the answer.

3 2 1
10 100 1000
1 2
1 3

2110

Hint
Your country is {1,2} and you can establish diplomatic relations with {3}. Finally the stable value is 2110.

BestCoder Round #53 (div.1) ($)