CF2228F Momoyo and the Network

那座喧嚣的集市如今何处 ——无关联市场者 地下大环线网络是一个宏伟的交通系统，连接了幻想乡的每一个角落。Momoyo 注意到，这个网络的结构就像一棵树。她情不自禁地想象着拆解这棵树最有效的方法。 给定一棵包含 $n$ 个节点的树，第 $i$ 个节点的权值为 $a_i$。请你选择一条恰好包含 $k$ 条边的简单路径，并删除该路径上的所有边。这样会将树分成 $k+1$ 个连通块，每个连通块的权值等于其所有节点权值之和。你需要最大化所有连通块中最小的权值。如果不存在长度为 $k$ 的简单路径，则输出 $-1$。 *注：树是一个无环连通图。*

每组测试包含若干测试用例。第一行包含测试用例个数 $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$。

在第一个测试用例中，可以选择路径 $3 \to 4$，移除该路径后，得到权值分别为 $6$ 和 $4$ 的两个连通块。 在第四个测试用例中，可以选择路径 $1 \to 2 \to 5$，移除该路径后，得到的连通块权值分别为 $7$，$6$ 和 $9$。 由 ChatGPT 5 翻译