解题思路

设树上共有 $n$ 个点，每条边有一个正整数边权。由于树中任意两点之间的路径唯一，所以每一对点 $(u,v)$ 的路径最大边权也是唯一确定的。题目要求的是所有无序点对 $(u,v)$ 的路径最大边权之和。

题目内容

在一个国家的监控系统中，共有 $n$ 座哨所，哨所通过道路相连，构成一棵树。每条道路的风险系数以正整数表示，数值越大意味着道路越危险。

安全部门需要评估所有哨所对之间的最高风险等级之和，以便制定应急预案。

给定一棵有 $n$ 个节点的树，节点编号 $1 \sim n$ ，每条边带有一个正整数权值。

定义节点间路径的最大权值为该路径上所有边权的最大值。请计算所有无序节点对 $(u, v)$ （ $1 \le u < v \le n$ ）的路径最大权值之和。由于答案可能很大，请将答案对 $(10^9 + 7)$ 取模后输出。

【名词解释】树：树是一个连通无环的无向图。

路径：路径是指一系列边连接起来的节点序列，节点之间相邻且不重复。

路径最大权值：路径最大权值指路径上所有边权的最大值，即最危险道路的风险系数。

第一行输入一个整数 $n$ （ $2 \le n \le 2 \times 10^5$ ），表示节点数；

接下来 $n - 1$ 行，每行输入三个整数 $u, v, w$ （ $1 \le u, v \le n$ ， $1 \le w \le 10^9$ ），表示节点 $u$ 与节点 $v$ 之间存在一条权值为 $w$ 的无向边。

输出一个整数，表示所有无序节点对 $(u, v)$ 的路径最大权值之和对 $10^9 + 7$ 的结果。

输入

输出

说明

在此样例中，所有 $\binom{5}{2} = 10$ 对节点的路径最大权值分别为：

$(1, 2), (2, 3), (3, 4), (4, 5)$ 最大值 $3, 1, 4, 2$ ；
$(1, 3), (2, 4), (3, 5)$ 最大值 $3, 4, 4$ ；
$(1, 4), (2, 5), (1, 5)$ 最大值 $4, 4, 4$ ；总和 $= 3 + 1 + 4 + 2 + 3 + 4 + 4 + 4 + 4 + 4 = 33$ 。

输入

输出