CF2275G Copper Squander

K1o0n 接受了一个另类的结局，并在程序部找到了一份工作。众所周知，所有程序员都懂得如何为电缆挖沟，因此他的第一个任务便是为大学各建筑之间布线——并且他有幸可以自行处理这些旧电缆换取收益。 大学里有 $n$ 栋建筑，而其中一些建筑之间已经敷设了电缆——总共有 $m$ 根电缆。数据可以在第 $i$ 根电缆上双向传输；它连接着建筑 $u_i$ 和 $v_i$，其中含有价值 $d_i$ 金币的铜。网络的布设都是在 K1o0n 到来之前完成的，当时没人关心花费：有些地方多装了一根跳线，有些用了更贵的电缆，有的楼甚至根本没连上。 现在网络可以按如下顺序重建： 1. 拆除任意一些电缆。被移除的第 $i$ 根电缆中的铜会送去回收站，可以获得 $d_i$ 金币；该电缆所连的建筑之间将不再连通。 2. 可以在任意两栋不同的楼之间新铺任意数量的电缆。K1o0n 亲自负责挖沟，但电缆的安装由施工队完成，而且他们胃口很大，每申请一次费用就涨一倍：第 1 根新电缆需要 $x$ 金币，第 2 根 $2x$ 金币，第 3 根 $3x$ 金币，依此类推。 操作完成后，网络必须是连通的：从任意一栋楼都可以通过某些电缆到达其它任意一栋楼。注意，最初的网络有可能本身就不连通。 利润为：回收铜线所得的收入减去新电缆安装的费用。 现在给定 $q$ 组不同的场景，第 $j$ 个场景中新电缆的安装增长费用为 $x_j$。对于每个场景，求出能够获得的最大利润。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $q$（$2 \le n \le 10^5$，$0 \le m \le 2 \cdot 10^5$，$1 \le q \le 2 \cdot 10^5$），分别表示建筑的数量、电缆的数量和场景的数量。 接下来 $m$ 行，每行包含三个整数 $u_i$、$v_i$、$d_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$，$1 \le d_i \le 5 \cdot 10^8$），表示第 $i$ 根电缆连接的两栋不同建筑及其铜线价值。不存在一对建筑之间有多根电缆，也不存在自环。 每个测试用例的最后一行包含 $q$ 个整数 $x_1, x_2, \ldots, x_q$（$1 \le x_j \le 5 \cdot 10^8$），分别代表每个场景中新电缆安装费用的递增单价。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，$m$ 的总和不超过 $2 \cdot 10^5$，$q$ 的总和不超过 $2 \cdot 10^5$。

对于每个场景，输出一个整数，表示最大利润。请按输入给出的场景顺序，在一行内输出对应的答案，用空格分隔。

由 ChatGPT 5 翻译