P17395 [ICPC 2018 Shenyang R] Diameter of a Tree

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

在第二个样例中： * $T_0$ 的直径为 $105$，是路径 $1 - 2 - 3$ 的长度； * $T_5$ 的直径为 $117$，是路径 $1 - 2 - 4 - 5$ 的长度。 翻译由 DeepSeek V4 Pro 完成