Person in Charge

Problem Description

Little Jiandan is learning discrete mathematics, and today's content is the basics of graph theory. In class, he made the following two notes:

1. A tree of size $n$ consists of $n$ nodes and $n - 1$ undirected edges, and satisfies that there is exactly one simple path between any two nodes. If a node and its associated edges are removed from the tree, the tree will split into several subtrees; if an edge is removed from the tree (retaining the associated nodes, the 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 the centroid of the tree if and only if after removing $c$ and its associated edges from the tree, the size of all split subtrees is no more than $\lfloor \frac{n}{2} \rfloor$ (where $\lfloor x \rfloor$ is the floor function). For a tree containing at least one node, it can have only 1 or 2 centroids.

After class, the teacher gave a tree $S$ of size $n$, where the nodes are numbered from $1 \sim n$. Little Jiandan's homework is to find the sum of the sums of the centroid numbers of the two split subtrees after removing each edge of $S$ individually. That is:

$$\sum_{(u,v) \in E} \left( \sum_{1 \le x \le n \atop \text{and node } x \text{ is the centroid of } S'_u} x + \sum_{1 \le y \le n \atop \text{and node } y \text{ is the centroid of } S'_v} y \right)$$

In the above formula, $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$ respectively represent the split subtrees containing node $u$ and node $v$ after removing edge $(u,v)$ from tree $S$.

Little Jiandan finds the homework not easy at all, so he has to ask you for help. Please teach him how to solve it.

Input Format

This problem contains multiple test cases.

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

Then the input data for each test case is given in sequence. For each test case:

The first line contains an integer $n$ indicating the size of 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

There are $T$ lines in total, each with an integer. The integer in the $i$-th line represents: the sum of the sums of the centroid numbers of the two split subtrees after removing each edge individually from the tree given in the $i$-th test case.

Samples

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

Sample 1 Explanation

For the first test case:

• Removing edge $(1,2)$: the centroid number of the subtree containing node $1$ is $\{1\}$, and the centroid numbers of the subtree containing node $2$ are $\{2,3\}$.
• Removing edge $(2,3)$: the centroid number of the subtree containing node $2$ is $\{2\}$, and the centroid numbers of the subtree containing node $3$ are $\{3,5\}$.
• Removing edge $(2,4)$: the centroid numbers of the subtree containing node $2$ are $\{2,3\}$, and the centroid number of the subtree containing node $4$ is $\{4\}$.
• Removing edge $(3,5)$: the centroid number of the subtree containing node $3$ is $\{2\}$, and the centroid number of the subtree containing node $5$ is $\{5\}$.

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

Data Range

Test Case 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 "Special Property" column of the table, the meanings of the two properties are as follows: there exists a permutation $p_i (1 \le i \le n)$ of $1 \sim n$ such that:

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

For $100\%$ of the data, $1 \le T \le 5 , 1 \le u_i,v_i \le n$. It is guaranteed that the given graph is a tree.