注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "railroad2.h"。

输入格式

题目译自 2024년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T4 「철도 2」

IOI 国有 $N$ 个城市和连接这些城市的 $N-1$ 条双向铁路，任意两个不同的城市都可以通过铁路互相到达。也就是说，IOI 国的铁路网络是一个树结构。城市编号从 $0$ 到 $N-1$，铁路编号从 $0$ 到 $N-2$。对于每条编号为 $i$ 的铁路，它连接了编号为 $U[i]$ 和 $V[i]$ 的城市，长度为 $W[i]$。

在 IOI 国的任何一个城市出发，都可以乘坐直达列车直接到达另一个城市。也就是说，对于所有 $u,v$ $(0 \leq u, v \leq N-1, u \neq v)$ 的 $N(N-1)$ 个城市对 $(u, v)$，从 $u$ 城市出发到达 $v$ 城市的直达列车存在。乘坐这趟直达列车时，直到到达 $v$ 城市之前不能下车，这趟列车的耗时等于 IOI 国铁路网络中从 $u$ 城市到 $v$ 城市的唯一简单路径上所有铁路的长度之和。

作为铁路爱好者，你喜欢长时间乘坐一列火车，享受悠闲的时光。因此，乘坐耗时长的直达列车会让你感到更大的乐趣。

具体来说，对于两个不同的城市 $x, y$，乐趣 $\operatorname{joy}(x, y)$ 定义为满足以下条件的最大正整数 $D$：

• 从 $x$ 城市出发，乘坐耗时至少为 $D$ 的直达列车，经过有限次后到达 $y$ 城市。

你需要编写一个程序，计算满足 $0 \leq x, y \leq N-1, x \neq y$ 的所有 $N(N-1)$ 个城市对 $(x, y)$ 的 $\operatorname{joy}(x, y)$ 之和，并对 $1000000007\left(=10^{9}+7\right)$ 取模。

实现细节

你需要实现以下函数：

int travel(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]$ 的铁路。
• 该函数需要返回满足 $0 \leq x, y \leq N-1, x \neq y$ 的所有 $N(N-1)$ 个城市对 $(x, y)$ 的 $\operatorname{joy}(x, y)$ 之和，并对 $1000000007\left(=10^{9}+7\right)$ 取模。

注意，提交的代码中不应包含任何输入输出操作。

样例 1

考虑 $N=5, U=[0,1,0,0], V=[1,2,3,4], W=[1,2,3,2]$ 的情况。

评测程序将调用如下函数：

travel([0,1,0,0], [1,2,3,4], [1,2,3,2]);

下图展示了城市和铁路的布局：

计算 $x$ 城市和 $y$ 城市之间直达列车的耗时如下表所示：

计算所有可能的 $(x, y)$ 城市对的 $\operatorname{joy}(x, y)$ 如下表所示：

• $\operatorname{joy}(0,1)=3$。从 $0$ 城市出发，乘坐直达列车到 $2$ 城市，再乘坐直达列车到 $4$ 城市，最后乘坐直达列车到 $1$ 城市。三趟直达列车的耗时分别为 $3,5,4$。
• $\operatorname{joy}(1,2)=4$。从 $1$ 城市出发，乘坐直达列车到 $3$ 城市，再乘坐直达列车到 $2$ 城市。两趟直达列车的耗时分别为 $4$ 和 $6$。
• $\operatorname{joy}(2,3)=6$。从 $2$ 城市出发，乘坐直达列车到 $3$ 城市。这趟直达列车的耗时为 $6$。

函数应返回 80。

样例 2

考虑 $N=5, U=[0,0,0,0], V=[1,2,3,4], W=[3,2,2,1]$ 的情况。

评测程序将调用如下函数：

travel([0, 0, 0, 0], [1,2,3,4], [3,2,2,1]);

计算所有可能的 $(x, y)$ 城市对的 $\operatorname{joy}(x, y)$ 如下表所示：

函数应返回 78。

样例 3

考虑 $N=6, U=[0,1,2,3,4], V=[1,2,3,4,5], W=[3,1,4,1,5]$ 的情况。

评测程序将调用如下函数：

travel([0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [3, 1, 4, 1, 5]);

计算所有可能的 $(x, y)$ 城市对的 $\operatorname{joy}(x, y)$ 如下表所示：

函数应返回 284。

数据范围与提示

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

• $2 \leq N \leq 5\cdot 10^5$
• IOI 国的铁路网络是一个树结构
• 对于所有 $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$	$3$	$N \leq 50$
$2$	$6$	$N \leq 500$
$3$	$19$	$N \leq 2000$
$4$	$5$	$N \leq 8000$； 对于所有 $i$ $(0 \leq i \leq N-2)$，$U[i]=0$
$5$	$7$	$N \leq 8000$； 对于所有 $i$ $(0 \leq i \leq N-2)$，$U[i]=i, V[i]=i+1$
$6$	$15$	$N \leq 8000$
$7$	$4$	对于所有 $i$ $(0 \leq i \leq N-2)$，$U[i]=0$
$8$	$11$	对于所有 $i$ $(0 \leq i \leq N-2)$，$U[i]=i ; V[i]=i+1$
$9$	$30$	无附加限制

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2+i$ $(0 \leq i \leq N-2)$ 行：$U[i]\,V[i]\,W[i]$

示例评测程序将输出：

• 第 $1$ 行：travel 函数返回的值

注意，示例评测程序可能与实际评测程序不同。