CF2209F Dynamic Values And Maximum Sum

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.

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 $ .

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

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 $ .