9580: 奇袭

我军正在与敌方作战，并计划在一次奇袭行动中对敌方的物资补给造成严重打击。敌方共有 $n$ 个军营，它们通过 $n-1$ 条双向运输道路相连，并且任意两个军营之间都存在唯一的一条最短路径，该路径不会经过重复的道路。根据可靠情报，第 $i$ 个军营储备有价值为 $w_i$ 的战略物资。 为了削弱敌方的补给能力，我方计划摧毁一些运输道路。袭击行动的具体方案如下：我方将选择两个敌方军营 $x$ 和 $y$，要求从 $x$ 到 $y$ 的最短路径上包含恰好 $k$ 条道路。之后，我方将派遣无人机部队，摧毁从 $x$ 到 $y$ 的最短路径上的所有 $k$ 条道路。 袭击完成后，敌方的军营将被分割成若干个相互隔离的区域，我们称之为封锁区。具体地说，封锁区是指这样的一组军营：其中的任意两个军营之间仍然存在可达路径，而该组军营与其他军营之间的所有通路都被摧毁。 每个封锁区的"物资储备量"是该区域内所有军营的战略物资价值总和。定义敌军的"威胁值"为含有最多物资储备的封锁区的物资储备量。为有效防止敌方反扑，我方希望制定最优的袭击计划，使得在袭击完成后，敌军的威胁值尽可能小。请计算这一最小可能值。 输入保证至少存在一种可行的袭击方案。

本题共有 $T=10$ 组测试数据，每组测试数据的范围如下。敌军的军营数量满足 $1 \leq n \leq 10^5$，我方计划摧毁的道路数量满足 $2 \leq k \leq 20$，每个军营的物资储备量满足 $1 \leq w_i \leq 10^7$，并保证所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$。 输入格式如下，第一行包含一个整数 $T$，表示测试数据的组数。 对于每组测试数据： - 第一行包含两个整数 $n$ 和 $k$，分别表示军营的数量和可摧毁的道路数 - 第二行包含 $n$ 个整数 $w_1,w_2,...,w_n$，表示每个军营的物资储备量 - 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示军营 $u$ 和军营 $v$ 之间存在一条双向道路 保证任意两个军营之间存在唯一的最短路径。

对于每组测试数据，输出一个整数，表示在最优的摧毁方案下，敌军威胁值的最小可能值。 每组测试数据的输出结果应占据一行，按照输入顺序依次输出。

可以取 $x=7$, $y=6$，这两个军营之间的最短路径恰好包含 $4$ 条道路。这样，袭击结束后，我们有如下封锁区： - $\{7\}$ - $\{4,8\}$ - $\{2,9\}$ - $\{1,3,5\}$ - $\{6\}$ 其中封锁区 $\{1,3,5\}$ 的物资储备量最大，为 $12$，这就是敌军的威胁值。可以证明，没有其他袭击方案能让这个值更小