← 返回题目列表

Codeforces · 2228/F

F. Momoyo 和网络

中文机器翻译题面 查看原题

那个繁华的市场现在在哪里
— 不相关的营销人员

地下大线网络是连接幻想乡各个角落的大型交通系统。 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$$$。

示例

输入
复制

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

注意

在第一个测试用例中,考虑路径 $$$3\to4$$$。删除此路径会产生权重 $$$6$$$ 和 $$$4$$$ 的分量。

在第四个测试用例中,采用路径 $$$1\to2\to5$$$。删除此路径会产生权重 $$$7$$$、$$$6$$$ 和 $$$9$$$ 的分量。