设树上共有 n 个点,每条边有一个正整数边权。由于树中任意两点之间的路径唯一,所以每一对点 (u,v) 的路径最大边权也是唯一确定的。题目要求的是所有无序点对 (u,v) 的路径最大边权之和。
本题的核心算法是:
在一个国家的监控系统中,共有 n 座哨所,哨所通过道路相连,构成一棵树。每条道路的风险系数以正整数表示,数值越大意味着道路越危险。
安全部门需要评估所有哨所对之间的最高风险等级之和,以便制定应急预案。
给定一棵有 n 个节点的树,节点编号 1∼n,每条边带有一个正整数权值。
定义节点间路径的最大权值为该路径上所有边权的最大值。请计算所有无序节点对 (u,v)(1≤u<v≤n)的路径最大权值之和。由于答案可能很大,请将答案对 (109+7) 取模后输出。
【名词解释】 树:树是一个连通无环的无向图。
路径:路径是指一系列边连接起来的节点序列,节点之间相邻且不重复。
路径最大权值:路径最大权值指路径上所有边权的最大值,即最危险道路的风险系数。
第一行输入一个整数 n(2≤n≤2×105),表示节点数;
接下来 n−1 行,每行输入三个整数 u,v,w(1≤u,v≤n,1≤w≤109),表示节点 u 与节点 v 之间存在一条权值为 w 的无向边。
输出一个整数,表示所有无序节点对 (u,v) 的路径最大权值之和对 109+7 的结果。
输入
5
1 2 3
2 3 1
3 4 4
4 5 2
输出
33
说明
在此样例中,所有 (25)=10 对节点的路径最大权值分别为:
输入
4
1 2 5
2 3 2
3 4 3
输出
23