P11345 [KTSC 2023 R2] 基地简化

**请勿用 C++14 (GCC 9) 提交。** 请在程序开头加入如下代码： ```cpp #include int maintenance_costs_sum(std::vector U, std::vector V, std::vector W); ```

**题目译自 [2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2023/) T1 「[기지 간소화](https://assets.ioikorea.kr/ioitst/2023/2/base/base_statement.pdf)」** 在遥远的未来，人类已经扩展到许多外星行星。行星 X 是其中之一，宇宙探险公司 MR 在行星 X 上建立了基地，进行探险和资源采集活动。 行星 X 上有 $N$ 个基地和连接这些基地的 $N-1$ 条双向通道，任意两个不同的基地都可以通过这些通道互相到达。也就是说，行星 X 的基地和通道构成了一棵树。 每个基地都有一个编号，从 $0$ 到 $N-1$。对于每个 $i$ $(0 \leq i \leq N-2)$，第 $i$ 条通道连接 $U[i]$ 号基地和 $V[i]$ 号基地，通道的长度为 $W[i]$ 公里。 随着行星 X 的开发逐渐稳定，维护所有基地和通道的成本变得很高，因此 MR 决定只保留部分基地，其他的将被停用。 假设只保留编号为 $s$ 到 $e$ 的基地 $(0 \leq s \leq e \leq N-1)$。此时的维护成本定义如下： - 选择 $0$ 条或更多的通道，使得以下条件得到满足，并且选择的通道长度之和最小（选择 $0$ 条通道时，长度之和为 $0$ 公里）。 - 对于任意 $u, v$ $(s \leq u < v \leq e)$，$u$ 号基地和 $v$ 号基地可以通过选择的通道互相到达，中间经过停用的基地也没关系。 - 选择的通道长度之和为 $C$ 公里时，维护成本为 $C$。 由于尚未决定保留哪些基地，MR 希望知道所有可能的 $(i, j)$ $(0 \leq i \leq j \leq N-1)$ 组合下，只保留编号为 $i$ 到 $j$ 的基地时的维护成本之和。你需要为 MR 计算这个值。由于结果可能非常大，请对 $1000000007$ 取模。 你需要实现以下函数： ```cpp int maintenance_costs_sum(vector U, vector V, vector W); ``` - 该函数只会被调用一次。 - `U, V, W`：大小为 $N-1$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-2)$，$U[i]$ 号基地和 $V[i]$ 号基地之间有一条长度为 $W[i]$ 公里的通道。 - 该函数返回所有可能的 $(i, j)$ $(0 \leq i \leq j \leq N-1)$ 组合下，只保留编号为 $i$ 到 $j$ 的基地时的维护成本之和，对 $1000000007$ 取模的结果。 注意，提交的代码中不应包含任何输入输出操作。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N$ - 第 $2+i$ $(0 \leq i \leq N-2)$ 行：$U[i]\,V[i]\,W[i]$

示例评测程序按以下格式输出： - 第 $1$ 行：函数 `maintenance_costs_sum` 返回的值

对于所有输入数据，满足： - $2 \leq N \leq 2.5\cdot 10^5$ - 对于所有 $i$ $(0 \leq i \leq N-2)$，$0 \leq U[i], V[i] \leq N-1 ; U[i] \neq V[i]$ - 对于所有 $i$ $(0 \leq i \leq N-2)$，$1 \leq W[i] \leq 10^9$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $5$ | $N \leq 300$ | | $2$ | $6$ | $N \leq 4000$ | | $3$ | $10$ | 基地的编号是以 $0$ 号基地为根的树的前序遍历顺序之一 | | $4$ | $26$ | 每个基地最多连接 $2$ 条通道 | | $5$ | $53$ | 无附加限制 |