Background

Original problem link: https://oier.team/problems/J2D.

Problem Description

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$.

Input Format

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 Format

Output one line containing one integer, representing the answer.

4
1 2
1 3
1 4

9

6
1 2
2 3
3 4
4 5
5 6

70

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

536

Hint

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.

For all testdata, $2 \le n \le 2 \cdot 10^5$, and the input graph is a tree.

Translated by ChatGPT 5