CF2229I The Endians

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$: $S = \{2 ,4, 6\}$; the score is $(12 + 6 + 7) + (6 + 7) + (7) = 45$. In the second test case, $S = \{1, 2, 3, 4, 5\}$ for all $x$.