P10842 [MX-J2-T3] Piggy and Trees

Original problem link: .

You are given a tree with $n$ nodes. Define $f(u, v, i)$ as the minimum value of $\text{dis}(x, i)$ among all nodes $x$ that satisfy $^\dagger\text{dis}(u, x) + \text{dis}(v, x) = \text{dis}(u, v)$. Compute $\sum\limits_{u = 1}^n \sum\limits_{v = u + 1}^n \sum\limits_{i = 1}^n f(u, v, i)$ modulo $10^9 + 7$. $^\dagger\text{dis}(u, v)$ is the length of the path between nodes $u$ and $v$ in the tree. In particular, $\text{dis}(u, u) = 0$.

The first line contains an integer $n$, representing the number of nodes in the tree. Each of the following $n - 1$ lines contains two integers $u_i, v_i$, representing an edge in the tree.

Output one line containing one integer, representing the answer.

#### Sample Explanation In sample $1$, all non-zero values of $f(u, v, i)$ are: - $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$. #### Constraints **This problem uses bundled testdata and subtask dependencies are enabled.** | Subtask ID | Score | $n \le$ | Special Property | Dependencies | | :-: | :-: | :-: | :-: | :-: | | $1$ | $8$ | $50$ | None | None | | $2$ | $15$ | $400$ | None | $1$ | | $3$ | $24$ | $3000$ | None | $1, 2$ | | $4$ | $17$ | $2 \cdot 10^5$ | $u_i = i, v_i = i + 1$ | None | | $5$ | $36$ | $2 \cdot 10^5$ | None | $1, 2, 3, 4$ | For all testdata, $2 \le n \le 2 \cdot 10^5$, and the input graph is a tree. Translated by ChatGPT 5