Вам дано дерево из $$$n$$$ вершин, где вершина $$$i$$$ имеет вес $$$w_i$$$, а также целое число $$$k$$$.
Пусть корнем дерева является вершина $$$x$$$. Вы можете выбрать подмножество вершин $$$S$$$ такое, что $$$|S| = k$$$ и $$$x \in S$$$. Пусть $$$f(i)$$$ — сумма весов всех вершин из $$$S$$$, лежащих на пути от вершины $$$i$$$ до корня. Счётом подмножества $$$S$$$ называется величина $$$\sum_{i \in S} f(i)$$$.
Для каждой вершины $$$1 \le x \le n$$$ найдите максимальный возможный счёт среди всех подмножеств $$$S$$$, если бы корнем дерева была вершина $$$x$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 4000$$$, $$$1 \le k \le n$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$w_1, w_2,\ldots, w_n$$$ ($$$1 \le w_i \le 10^9$$$).
Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$), указывающих на то, что вершины $$$u$$$ и $$$v$$$ соединены ребром. Гарантируется, что заданный граф является деревом.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$4000$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел. Для каждого $$$x$$$ от $$$1$$$ до $$$n$$$ выведите максимально возможный счёт среди всех подмножеств $$$S$$$, если бы корнем дерева была вершина $$$x$$$.
36 32 12 3 6 9 71 21 33 44 54 65 510000 1000 100 10 11 22 33 43 59 57 11 5 16 13 10 12 9 158 11 63 74 66 76 59 12 8
27 57 30 39 51 4554311 15311 12511 12451 12415120 150 134 170 155 122 150 132 162
В первом наборе входных данных дерево выглядит следующим образом:
Для каждого $$$1 \le x \le n$$$ одним из оптимальных подмножеств $$$S$$$ является:
- $$$x = 1$$$: $$$S = \{1, 2, 5\}$$$; счёт равен $$$(2) + (12 + 2) + (9 + 2) = 27$$$,
- $$$x = 2$$$: $$$S = \{2, 4 ,5\}$$$; счёт равен $$$(12) + (6 + 12) + (9 + 6 + 12) = 57$$$,
- $$$x = 3$$$: $$$S = \{2, 3, 5\}$$$; счёт равен $$$(12 + 3) + (3) + (9 + 3) = 30$$$,
- $$$x = 4$$$: $$$S = \{2, 4, 5\}$$$; счёт равен $$$(12 + 6) + (6) + (9 + 6) = 39$$$,
- $$$x = 5$$$: $$$S = \{2, 4 ,5\}$$$; счёт равен $$$(12 + 6 + 9) + (6 + 9) + (9) = 51$$$,
- $$$x = 6$$$: $$$S = \{2 ,4, 6\}$$$; счёт равен $$$(12 + 6 + 7) + (6 + 7) + (7) = 45$$$.
Во втором наборе входных данных $$$S = \{1, 2, 3, 4, 5\}$$$ для всех $$$x$$$.
