Description

Xiaojiandan is learning discrete mathematics. Today’s topic is basic graph theory, and in class he wrote down the following two notes:

1. A tree of size $n$ consists of $n$ nodes and $n - 1$ undirected edges, and between any two nodes there exists exactly one simple path. If you delete one node in a tree and all edges incident to it, the tree will split into several subtrees. If you delete one edge in a tree (keeping its incident nodes; same below), the tree will split into exactly two subtrees.
2. For a tree of size $n$ and any node $c$ in the tree, $c$ is called a centroid of the tree if and only if, after deleting $c$ and all edges incident to it, the sizes of all resulting subtrees are no more than $\lfloor \frac{n}{2} \rfloor$ (where $\lfloor x \rfloor$ is the floor function). For any tree with at least one node, it can have only 1 or 2 centroids.

After class, the teacher gave a tree $S$ of size $n$, with nodes numbered from $1$ to $n$. Xiaojiandan’s homework is to compute, for every edge deleted individually from $S$, the sum of the centroid node labels of the two resulting subtrees. That is:

$$\sum_{(u,v) \in E} \left( \sum_{1 \leq x \leq n \atop 且 x 号点是 S'_u 的重心} x + \sum_{1 \leq y \leq n \atop 且 y 号点是 S'_v 的重心} y \right)$$

In the expression above, $E$ denotes the edge set of tree $S$, and $(u,v)$ denotes an edge connecting node $u$ and node $v$. $S'_u$ and $S'_v$ denote, respectively, the two subtrees containing node $u$ and node $v$ after deleting edge $(u,v)$ from $S$.

Xiaojiandan finds this homework not simple at all, so he asks you for help. Please teach him.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, indicating the number of test cases.

Then the input for each test case is given as follows:

The first line contains an integer $n$, indicating the size of the tree $S$.

The next $n - 1$ lines each contain two integers $u_i$ and $v_i$ separated by a space, representing an edge $(u_i,v_i)$ in the tree.

Output Format

Output $T$ lines. Each line contains one integer. The integer on line $i$ means: for the tree given in test case $i$, after deleting each edge individually, the sum of the centroid node labels of the two resulting subtrees.

2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7

32
56

Hint

[Sample 1 Explanation]

For the first test case:

Delete edge $(1,2)$. The centroid labels of the subtree containing node 1 are $\{1\}$. The centroid labels of the subtree containing node 2 are $\{2,3\}$.

Delete edge $(2,3)$. The centroid labels of the subtree containing node 2 are $\{2\}$. The centroid labels of the subtree containing node 3 are $\{3,5\}$.

Delete edge $(2,4)$. The centroid labels of the subtree containing node 2 are $\{2,3\}$. The centroid labels of the subtree containing node 4 are $\{4\}$.

Delete edge $(3,5)$. The centroid labels of the subtree containing node 3 are $\{2\}$. The centroid labels of the subtree containing node 5 are $\{5\}$.

Therefore, the answer is $1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32$.

[Constraints]

Test Point ID	$n =$	Special Property
$1 \sim 2$	$7$	None
$3 \sim 5$	$199$
$6 \sim 8$	$1999$
$9 \sim 11$	$49991$	A
$12 \sim 15$	$262143$	B
$16$	$99995$	None
$17 \sim 18$	$199995$
$19 \sim 20$	$299995$

In the table, the meanings of the two special properties are that there exists a permutation $p_i (1 \leq i \leq n)$ of $1 \sim n$ such that:

• A: The tree is a chain. That is, $\forall 1 \leq i \lt n$, there exists an edge $(p_i, p_{i + 1})$.
• B: The tree is a perfect binary tree. That is, $\forall 1 \leq i \leq \frac{n-1}{2}$, there exist two edges $(p_i, p_{2i})$ and $(p_i, p_{2i+1})$.

For all test points: $1 \leq T \leq 5$, $1 \leq u_i,v_i \leq n$. It is guaranteed that the given graph is a tree.

Translated by ChatGPT 5