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.
Input
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$.
Output
For each test case, output the maximum possible minimum component weight, or $-1$ if no such path exists.
Note
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$.
样例
5
4 1
1 2 3 4
1 2
2 3
3 4
4 2
1 2 3 4
1 2
2 3
3 4
4 3
1 2 3 4
1 2
2 3
3 4
7 2
7 1 3 2 2 4 3
1 2
2 3
2 4
2 5
5 6
5 7
4 3
1 2 3 4
1 2
1 3
1 4
4
3
1
6
-1
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。