CF733F Drivers Dissatisfaction

在一个王国中有 $n$ 个城市和 $m$ 条双向道路。每条道路连接一对城市，对于每条道路，我们知道驾驶员的不满值 $w_{i}$。 对于每条道路，还给定 $c_{i}$，表示将该道路的不满值减少 $1$ 需要花费多少 lamzik。因此，要将第 $i$ 条道路的不满值减少 $k$，需花费 $k \cdot c_{i}$ 个 lamzik。不满值可以减少到 $0$，也允许为负值。 根据国王的命令，我们需要选择 $n-1$ 条道路作为主干道。一个重要的条件是：必须能够通过主干道从任意一个城市到达其他城市。 道路部门有 $S$ 个 lamzik 的预算用于改革。部门准备将这笔预算用于修缮某些道路（即降低它们的不满值），然后选择 $n-1$ 条主干道。 请帮助他们合理使用预算，使得主干道的总不满值最小。不满值允许为负数，也不一定要把预算 $S$ 全部花完。 保证任意两城之间都可以通过现有道路连通。王国中的每条道路都是双向的。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^{5}$，$n-1 \leq m \leq 2 \cdot 10^{5}$），表示王国中的城市数量和道路数量。 第二行包含 $m$ 个整数 $w_1, w_2, \ldots, w_m$（$1 \leq w_i \leq 10^9$），其中 $w_i$ 表示第 $i$ 条道路的驾驶员不满值。 第三行包含 $m$ 个整数 $c_1, c_2, \ldots, c_m$（$1 \leq c_i \leq 10^9$），其中 $c_i$ 表示将第 $i$ 条道路的不满值减少 $1$ 所需的 lamzik 数。 接下来 $m$ 行描述道路信息。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \ne b_i$），表示第 $i$ 条道路连接城市 $a_i$ 和 $b_i$。所有道路为双向，可以从 $a_i$ 到 $b_i$，也可以从 $b_i$ 到 $a_i$。同一对城市可能有多条道路直接连接。 最后一行包含一个整数 $S$（$0 \leq S \leq 10^9$），表示可用来进行道路改革的 lamzik 总数。

第一行输出一个整数 $K$，表示主干道的最小总不满值。 接下来的 $n-1$ 行，每行输出两个整数 $x, v_x$，表示第 $x$ 条道路被选为主干道，并且经过改革后该道路的不满值为 $v_x$。 假定道路编号为 $1$ 到 $m$，按输入顺序编号。输出的道路顺序任意。如果有多组答案，输出其中任意一组均可。

由 ChatGPT 5 翻译