Solve the programming task below in a Python markdown code block.
Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a rooted tree with $N$ nodes (numbered $1$ through $N$); node $1$ is the root. Each node has a value; let's denote the value of node $i$ by $A_{i}$.

You may perform the following operation any number of times (including zero): choose any node which still exists in the tree and remove the whole subtree of this node including itself.

Let's define the *profit* as the sum of values of all nodes which currently exist in the tree minus $X \cdot k$, where $k$ denotes the number of times this operation was performed. Find the maximum possible profit.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $X$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
Each of the following $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that nodes $u$ and $v$ are connected by an edge.

------  Output ------
For each test case, print a single line containing one integer — the maximum profit.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ X ≤ 10^{9}$
$1 ≤ u, v ≤ N$
$|A_{i}| ≤ 10^{9}$ for each valid $i$
the graph described on the input is a tree

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ N ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

3 5

1 -5 -10

1 2

2 3
----- Sample Output 1 ------ 
-4