You are given a tree of (n) nodes, where node (i) has weight (w_i), and an integer (k). Let the tree be rooted at node (x). You may select a subset (S) of the nodes such that (|S| = k) and (x \in S). Let (f(i)) be the sum of the weights of all nodes in (S) on the path from node (i) to the root. The score of (S) is (\sum_{i \in S} f(i)). For each node (1 \le x \le n), find the maximum possible score among all subsets (S) if the tree is rooted at node (x). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 500)). The description of the test cases follows. The first line of each test case contains two integers (n) and (k) ((2 \le n \le 4000), (1 \le k \le n)). The second line of each test case contains (n) integers (w_1, w_2,\ldots, w_n) ((1 \le w_i \le 10^9)). Each of the next (n - 1) lines contains two integers (u) and (v) ((1 \le u, v \le n)), indicating that nodes (u) and (v) are connected by an edge. It is guaranteed that the given graph is a tree. It is guaranteed that the sum of (n) over all test cases does not exceed (4000). For each test case, print (n) integers. For each (x) from (1) to (n), print the maximum possible score among all subsets (S) if the tree is rooted at node (x). In the first test case, the tree is as follows: For each (1 \le x \le n), the following is an optimal set (S): (x = 1): (S = \{1, 2, 5\}); the score is ((2) + (12 + 2) + (9 + 2) = 27), (x = 2): (S = \{2, 4 ,5\}); the score is ((12) + (6 + 12) + (9 + 6 + 12) = 57), (x = 3): (S = \{2, 3, 5\}); the score is ((12 + 3) + (3) + (9 + 3) = 30), (x = 4): (S = \{2, 4, 5\}); the score is ((12 + 6) + (6) + (9 + 6) = 39), (x = 5): (S = \{2, 4 ,5\}); the score is ((12 + 6 + 9) + (6 + 9) + (9) = 51), (x = 6):