P10842 【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$。

无

无

#### 【样例解释】 在样例 $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$，输入的图是一棵树。