【MX-J2-T3】Piggy and Trees
题目描述
给你一棵 $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$。
【数据范围】
本题采用捆绑测试且开启子任务依赖。
| 子任务编号 | 分值 | $n \le$ | 特殊性质 | 子任务依赖 |
|---|---|---|---|---|
| $1$ | $8$ | $50$ | 无 | 无 |
| $2$ | $15$ | $400$ | 无 | $1$ |
| $3$ | $24$ | $3000$ | 无 | $1, 2$ |
| $4$ | $17$ | $2 \cdot 10^5$ | $u_i = i, v_i = i + 1$ | 无 |
| $5$ | $36$ | $2 \cdot 10^5$ | 无 | $1, 2, 3, 4$ |
对于所有数据，满足 $2 \le n \le 2 \cdot 10^5$，输入的图是一棵树。C
