You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

树

题目描述

给你一棵 $n$ 个结点的树。

定义 $f(u, v, i)$ 为，在所有满足 $^\dagger\text{dis}(u, x) + \text{dis}(v, x) = \text{dis}(u, v)$ 的点 $x$ 中，$\text{dis}(x, i)$ 的最小值。

求 $\sum\limits_{u = 1}^n \sum\limits_{v = u + 1}^n \sum\limits_{i = 1}^n f(u, v, i)$ 对 $10^9 + 7$ 取模的值。

$^\dagger\text{dis}(u, v)$ 为树上 $u, v$ 两点的路径长度。特别地，$\text{dis}(u, u) = 0$。

输入格式

第一行包含一个整数 $n$，表示树的结点数。

之后的 $n - 1$ 行中的第 $i$ 行包含两个整数 $u_i, v_i$，表示树上的一条边。

输出格式

输出一行一个整数，表示答案。

样例 #1

样例输入 #1

4
1 2
1 3
1 4

样例输出 #1

9

样例 #2

样例输入 #2

6
1 2
2 3
3 4
4 5
5 6

样例输出 #2

70

样例 #3

样例输入 #3

10
1 2
1 3
1 4
2 5
3 6
2 7
4 8
8 9
9 10

样例输出 #3

536

提示

【样例解释】

在样例 $1$ 中，所有非 $0$ 的 $f(u, v, i)$ 的值为：

• $f(1, 2, 3) = 1$；
• $f(1, 2, 4) = 1$；
• $f(1, 3, 2) = 1$；
• $f(1, 3, 4) = 1$；
• $f(1, 4, 2) = 1$；
• $f(1, 4, 3) = 1$；
• $f(2, 3, 4) = 1$；
• $f(2, 4, 3) = 1$；
• $f(3, 4, 2) = 1$。

【数据范围】

本题采用捆绑测试且开启子任务依赖。

对于所有数据，满足 $2 \le n \le 2 \cdot 10^5$，输入的图是一棵树。