题目描述

给定一棵带权树 $T_0$，我们将其直径定义为树上两顶点之间最长路径的长度，其中一条路径的长度等于该路径上所有边的权重之和。

如果这棵树像蜘蛛一样伸展，或者像打哈欠的老虎一样舒展，它的直径也会随之变化。我们用 $T_i$ 表示经过 $i$ 秒后树的状态，此时每条边的权重相比于 $T_0$ 都恰好增加了 $i$ 个单位。

你将会面对若干不同的查询，对每次查询，你都需要计算在某个指定时刻这棵树的直径。

输入格式

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据的组数，最多不超过 $60$。

对于每组测试数据，第一行包含两个整数 $n$ 和 $m$，分别表示树中顶点的个数和给定查询的个数，满足 $2 \le n \le 2 \times 10^5$，$1 \le m \le 2 \times 10^5$。

接下来的 $(n - 1)$ 行，每行包含三个整数 $u, v$ 和 $w$，表示原树中连接第 $u$ 个顶点和第 $v$ 个顶点的一条权重为 $w$ 的边，满足 $1 \le u, v \le n$，$u \ne v$，$1 \le w \le 10^8$。

接下来的 $m$ 行，每行描述一个查询，包含一个整数 $k$，要求你计算树 $T_k$ 的直径，满足 $0 \le k \le 10^9$。

我们保证所有测试数据中 $n$ 的总和不超过 $10^6$，$m$ 的总和也不超过 $10^6$。

输出格式

对于每组测试数据，首先输出一行包含 “Case #x:”（不含引号），其中 $x$ 是测试数据的编号，从 $1$ 开始。

然后输出 $m$ 行与所有查询对应，其中第 $i$ 行包含一个整数，表示对第 $i$ 个查询的答案。

2
3 3
1 2 1
1 3 5
5
10
100
5 6
1 2 100
2 3 5
2 4 1
4 5 1
0
1
2
3
4
5

Case #1:
16
26
206
Case #2:
105
107
109
111
114
117

提示

在第二个样例中：

• $T_0$ 的直径为 $105$，是路径 $1 - 2 - 3$ 的长度；
• $T_5$ 的直径为 $117$，是路径 $1 - 2 - 4 - 5$ 的长度。

翻译由 DeepSeek V4 Pro 完成