Tree Centroid

Problem Source

CSP-S 2019

Problem Description

Xiao Jiandan is studying discrete mathematics. Today's topic is graph theory basics, and he wrote down two notes in class:

1. A tree of size $n$ consists of $n$ nodes and $n - 1$ undirected edges, and any two nodes are connected by exactly one simple path. Deleting a node and its incident edges from a tree splits it into several subtrees; deleting an edge (keeping its endpoints) splits the tree into exactly two subtrees.
2. For a tree of size $n$ and any node $c$ in it, $c$ is called a centroid of the tree if and only if, after deleting $c$ and its incident edges, every resulting subtree has size at most $\lfloor n/2 \rfloor$ (where $\lfloor x \rfloor$ is the floor function). A tree with at least one node has either $1$ or $2$ centroids.

After class, the teacher gives Xiao Jiandan a tree $S$ of size $n$, with nodes numbered from $1$ to $n$. His homework is to compute, for $S$ with every single edge removed, the sum of the centroid numbers of the two resulting subtrees. That is:

$$\sum_{(u,v) \in E} \left( \sum_{\substack{1 \le x \le n \\ \text{and } x \text{ is a centroid of } S_u'}} x + \sum_{\substack{1 \le y \le n \\ \text{and } y \text{ is a centroid of } S_v'}} y \right)$$

In the formula, $E$ is the edge set of tree $S$, and $(u, v)$ is an edge connecting node $u$ and node $v$. $S_u'$ and $S_v'$ denote the two subtrees into which $S$ is split after removing edge $(u, v)$, containing node $u$ and node $v$ respectively.

Xiao Jiandan finds the homework not simple at all, so he asks you for help.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 5$), the number of test cases.

For each test case:

• The first line contains an integer $n$ ($1 \le n \le 3 \times 10^5$), the size of tree $S$.
• The next $n - 1$ lines each contain two space-separated integers $u_i, v_i$, an edge of the tree.

Output Format

Output $T$ lines in total. The $i$-th line contains one integer: for the tree given in the $i$-th test case, the sum of the centroid numbers of the two subtrees split by removing every single edge.

Sample Input

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

Sample Output

32
56

Sample Explanation

For the first test case:

• Removing edge $(1, 2)$: the subtree containing node $1$ has centroid $\{1\}$; the subtree containing node $2$ has centroids $\{2, 3\}$.
• Removing edge $(2, 3)$: the subtree containing node $2$ has centroid $\{2\}$; the subtree containing node $3$ has centroids $\{3, 5\}$.
• Removing edge $(2, 4)$: the subtree containing node $3$ has centroids $\{2, 3\}$; the subtree containing node $4$ has centroid $\{4\}$.
• Removing edge $(3, 5)$: the subtree containing node $3$ has centroid $\{2\}$; the subtree containing node $5$ has centroid $\{5\}$.

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