P15048 [UOI 2022 II Stage] 树 2

哥萨克胡子在从铁路回家的路上看到一棵树，并由此想出了一道题。 给定一棵包含 $n$ 个顶点的树，每条边都有一定的权重。初始时，所有顶点都是白色的。我们称一条边为 **亮边**，如果它连接两个白色顶点。请回答 $m$ 个查询： - 需要将最少多少个顶点重新涂成黑色，才能使所有 **亮边** 的权重之和不超过 $k_i$？ 请帮助哥萨克胡子解决这个问题。

第一行包含三个整数 $n$、$m$ 和 $g$ ($1 \leq n \leq 3\,000$, $1 \leq m \leq 2 \cdot 10^5$, $0 \leq g \leq 6$) —— 分别表示顶点数量、查询数量以及子任务编号。 接下来的 $n-1$ 行，每行包含三个整数 $u_i$、$v_i$、$c_i$ ($1 \leq v_i, u_i \leq n$, $1 \leq c_i \leq 10^5$) —— 表示边连接的顶点及其权重。 第四行包含 $m$ 个整数 $k_1, k_2, \dots, k_m$ ($0 \leq k_i \leq 10^9$)。

输出 $m$ 个整数 $x_1, x_2, \dots, x_m$，其中 $x_i$ 是对第 $i$ 个查询的答案。

### 样例说明 在第一个样例中，如果 $k_i \geq 5$，我们可以保留所有顶点为白色，那么所有边都是 **亮边**，其权重之和为 $5$。对于 $k_i \leq 4$，我们可以将顶点 $1$ 涂成黑色，那么就没有 **亮边** 了，因此权重之和为 $0$。在这两种情况下，**亮边** 的权重之和都不超过 $k_i$，并且我们重新涂色的顶点数量是最少的。 ### 评分细则 - （5 分）： $m=1$；保证答案不超过 $1$。 - （9 分）： $m=1$；保证答案不超过 $2$。 - （28 分）： $u_i = v_i - 1$；$n \leq 200$。 - （14 分）： $m=1$；$n \leq 10$； - （21 分）： $n \leq 200$； - （23 分）： 无额外限制。 翻译由 DeepSeek V3 完成