题目描述

哥萨克胡子在从铁路回家的路上看到一棵树，并由此想出了一道题。

给定一棵包含 $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$ 个查询的答案。

3 5 0
1 2 3
1 3 2
3 5 1 2 0

1 0 1 1 1

4 4 0
1 3 10
2 1 15
1 4 50
75 50 72 19

0 1 1 1

5 8 0
1 4 5
2 1 18
1 3 9
3 5 27
5 15 7 19 20 58 35 27

2 2 2 2 2 1 1 1

提示

样例说明

在第一个样例中，如果 $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 完成