U745743 「加权距离」

> 注：本题的“**穷距点对**”概念受 [P8981「DROI」Round 1 距离](https://www.luogu.com.cn/problem/P8981) 启发。 > > 原题讨论的是无权树上的距离；本题将距离定义推广为边权之和，并相应调整了统计目标。题面文字与数据均为本题独立撰写，特此向学长致谢。 道有修短，步有轻重；自权值加诸边，距离遂不复以一程一步计。

给定一棵包含 $n$ 个结点的无向树，每条边有一个正整数权值 $w$。定义两点 $u, v$ 之间的距离 $\operatorname{dis}(u, v)$ 为两点之间唯一简单路径上所有边的权值之和。 若对于树上两点 $u, v$，满足 $\forall\, x \in G$ 都有 $\operatorname{dis}(u, x) \leq \operatorname{dis}(u, v)$ **且** $\operatorname{dis}(v, x) \leq \operatorname{dis}(u, v)$，则称无序点对 $(u, v)$ 为**穷距点对**。 同时，树 $G$ 上一点 $x$ 的权值 $f_x$ 定义为：**两点间唯一简单路径经过 $x$ 的穷距点对的数量**。 现给定树 $G$，求 $\sum\limits_{x \in G} f_x^2$ 对 $10^9+7$ 取模的值。

第一行一个整数 $n$，表示树 $G$ 的点数。 接下来 $n - 1$ 行，每行三个整数 $u, v, w$，表示点 $u$ 和点 $v$ 之间有一条权值为 $w$ 的边。

输出一行一个整数，表示答案对 $10^9+7$ 取模后的值。

### 样例 1 解释 唯一的穷距点对为 $(1, 2)$，其路径经过点 $1$ 和点 $2$，故 $f_1 = f_2 = 1$。答案为 $1^2 + 1^2 = 2$。 ### 样例 2 解释 树的直径为 $6$，穷距点对为 $(1, 5)$ 与 $(3, 5)$。 - 点对 $(1, 5)$ 的路径为 $1 \to 2 \to 4 \to 5$，经过点 $1, 2, 4, 5$； - 点对 $(3, 5)$ 的路径为 $3 \to 2 \to 4 \to 5$，经过点 $3, 2, 4, 5$。 故 $f_1 = 1$，$f_2 = 2$，$f_3 = 1$，$f_4 = 2$，$f_5 = 2$。答案为： $1^2 + 2^2 + 1^2 + 2^2 + 2^2 = 1 + 4 + 1 + 4 + 4 = 14$ ### 数据范围与提示 对于 $100\%$ 的数据，保证： - $1 \leq n \leq 5 \times 10^5$； - $1 \leq u, v \leq n$； - $1 \leq w \leq 10^9$； - 给出的图是一棵合法的树。 | 子任务 | 分值 | $n$ | 特殊限制 | | --- | --- | --- | --- | | 1 | 10 | $\leq 300$ | 无 | | 2 | 25 | $\leq 5000$ | 无 | | 3 | 30 | $\leq 10^5$ | 每个点度数 $\leq 200$ | | 4 | 35 | $\leq 5 \times 10^5$ | 无 | 本题输入量较大，请使用较快的输入方式。