题目背景

请勿用 C++14 (GCC 9) 提交。

请在程序开头加入如下代码：

#include<vector>
int maintenance_costs_sum(std::vector<int> U, std::vector<int> V, std::vector<int> W);

题目描述

题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T1 「기지 간소화」

在遥远的未来，人类已经扩展到许多外星行星。行星 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$ 取模。

你需要实现以下函数：

int maintenance_costs_sum(vector<int> U, vector<int> V, vector<int> 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 返回的值

5
0 2 2
2 1 3
2 4 6
0 3 5

98

提示

对于所有输入数据，满足：

• $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$	无附加限制