地下大线网络是连接幻想乡各个角落的大型交通系统。 Momoyo 注意到网络的布局类似于树$$$^{\text{*}}$$$ 结构。她不禁想象出最有效的方法来拆除那棵树。
给定一棵具有 $$$n$$$ 节点的树,其中节点 $$$i$$$ 的权重为 $$$a_i$$$,选择一条恰好包含 $$$k$$$ 边的简单路径,并删除其上的所有边。这会将树分割为 $$$k+1$$$ 连接的组件,每个组件的权重等于其节点权重的总和。您需要最大化最小组件权重,或者如果不存在恰好 $$$k$$$ 边的简单路径,则输出 $$$-1$$$。
$$$^{\text{*}}$$$树是没有环的连通图。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n-1$$$, $$$2 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数,其中第 $$$i$$$ 个整数表示 $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$)。
接下来的 $$$n-1$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$,表示树的一条边。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出最大可能的最小组件权重,如果不存在这样的路径,则输出 $$$-1$$$。
示例
输入复制
54 11 2 3 41 22 33 44 21 2 3 41 22 33 44 31 2 3 41 22 33 47 27 1 3 2 2 4 31 22 32 42 55 65 74 31 2 3 41 21 31 4
输出复制
4316-1
注意
在第一个测试用例中,考虑路径 $$$3\to4$$$。删除此路径会产生权重 $$$6$$$ 和 $$$4$$$ 的分量。
在第四个测试用例中,采用路径 $$$1\to2\to5$$$。删除此路径会产生权重 $$$7$$$、$$$6$$$ 和 $$$9$$$ 的分量。