F. Dynamic Values And Maximum Sum
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree$$$^{\text{∗}}$$$ with $$$n$$$ vertices numbered from 1 to $$$n$$$, where each vertex $$$i$$$ has an initial value $$$a_i$$$. You perform $$$k$$$ operations. The total is $$$0$$$ initially. In each operation:

  1. Choose a vertex $$$r$$$ and root the tree at $$$r$$$.
  2. Add the current value of $$$r$$$ to the total and set the value of $$$r$$$ to $$$0$$$.
  3. For each vertex $$$ u $$$ that is not a leaf$$$^{\text{†}}$$$, find the leaves in the subtree$$$^{\text{‡}}$$$ of $$$u$$$ that are at the maximum distance from $$$u$$$. Among them, select the one with the smallest index, denoted as the destination for $$$u$$$. Add the current value of $$$u$$$ to the destination and set the value of $$$u$$$ to $$$0$$$.
Find the maximum possible total.

$$$^{\text{∗}}$$$A tree is a connected graph without cycles.

$$$^{\text{†}}$$$A leaf is any vertex without children.

$$$^{\text{‡}}$$$A subtree of vertex $$$v$$$ is the subgraph of $$$v$$$, all its descendants, and all the edges between them.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10 ^ 4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial values of vertices.

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$, denoting an edge connecting vertex $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot 10 ^ 5$$$.

Output

For each test case, output an integer — the maximum possible total.

Example
Input
7
5 4
19 20 39 81 2
1 2
1 3
2 4
2 5
5 3
12 21 39 8 21
1 2
1 3
3 4
2 5
5 2
129 216 32 83 221
1 2
1 3
3 4
4 5
5 3
15 15 15 15 15
1 2
1 3
1 4
1 5
1 1
1
2 1
1 1000000000
1 2
7 2
8 3 5 7 9 1 6
4 3
7 5
5 2
2 3
3 6
6 1
Output
161
101
681
60
1
1000000000
32
Note

In the first test case:

  1. Choose vertex $$$1$$$ as the root. Add $$$a_1 = 19$$$ to the total and set $$$a_1 = 0$$$.

    After rooting the tree at $$$1$$$, for every non-leaf vertex $$$u$$$, move its value to the leaf in its subtree that is farthest from $$$u$$$ (breaking ties by smallest index). Under this rooting:

    • The value of vertex $$$2$$$ is transferred to vertex $$$4$$$, so $$$a_2$$$ becomes $$$0$$$ and $$$a_4$$$ becomes $$$101$$$.
    • The values of vertices $$$3$$$, $$$4$$$, and $$$5$$$ remain at their respective positions according to the rule.

  2. Choose vertex $$$3$$$ as the root. Add $$$a_3 = 39$$$ to the total and set $$$a_3 = 0$$$.

    After redistribution under this rooting, the values of vertices $$$4$$$ and $$$5$$$ remain at their positions.

  3. Choose vertex $$$4$$$ as the root. Add $$$a_4 = 101$$$ to the total and set $$$a_4 = 0$$$.

    After redistribution, the value at vertex $$$5$$$ remains unchanged.

  4. Choose vertex $$$5$$$ as the root. Add $$$a_5 = 2$$$ to the total and set $$$a_5 = 0$$$.

The total obtained is $$$19 + 39 + 101 + 2 = 161$$$.

In the sixth test case, choose vertex $$$2$$$ as the root. Add its value to the total, obtaining $$$1\,000\,000\,000$$$.