P5666 [CSP-S 2019] Tree Centroid

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.

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

[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$ | None | | $6 \sim 8$ | $1999$ | None | | $9 \sim 11$ | $49991$ | A | | $12 \sim 15$ | $262143$ | B | | $16$ | $99995$ | None | | $17 \sim 18$ | $199995$ | None | | $19 \sim 20$ | $299995$ | None | 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