CF2228F Momoyo and the Network

Where Is That Bustling Marketplace Now — Unconnected Marketeers The Underground Great Line Network is a grand transit system connecting all corners of Gensokyo. Momoyo noticed that the network's layout resembled a tree $ ^{\text{∗}} $ structure. She couldn't help but imagine the most effective way to dismantle that tree. Given a tree with $ n $ nodes where node $ i $ has weight $ a_i $ , select a simple path of exactly $ k $ edges and remove all edges on it. This splits the tree into $ k+1 $ connected components, each with weight equal to the sum of its nodes' weights. You need to maximize the minimum component weight, or output $ -1 $ if no simple path of exactly $ k $ edges exists. $ ^{\text{∗}} $ A tree is a connected graph without cycles.

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-1 $ , $ 2 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers, where the $ i $ -th integer represents $ a_i $ ( $ 1 \le a_i \le 10^9 $ ). The next $ n-1 $ lines each contain two integers $ u $ and $ v $ , representing an edge of the tree. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, output the maximum possible minimum component weight, or $ -1 $ if no such path exists.

In the first test case, consider the path $ 3\to4 $ . Removing this path yields components of weights $ 6 $ and $ 4 $ . In the fourth test case, take the path $ 1\to2\to5 $ . Removing this path yields components of weights $ 7 $ , $ 6 $ , and $ 9 $ .