【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$ 中，所有非 $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$ ，输入的图是一棵树。