树的重心

题目来源

CSP-S 2019

题目描述

小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:

1. 一个大小为 $n$ 的树由 $n$ 个结点与 $n − 1$ 条无向边构成,且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。
2. 对于一个大小为 n 的树与任意一个树中结点 $c$,称 $c$ 是该树的重心当且仅当在树中删去 $c$ 及与它关联的边后,分裂出的所有子树的大小均不超过 $\lfloor \frac{n}{2} \rfloor$(其中 $\lfloor x \rfloor$ 是下取整函数)。对于包含至少一个结点的树,它的重心只可能有 1 或 2 个。

课后老师给出了一个大小为 $n$ 的树 $S$ ,树中结点从 $1 \sim n$ 编号。小简单的课后作业是求出 $S$ 单独删去每条边后,分裂出的两个子树的重心编号和之和。即:

$$\sum \limits_{(u,v) \in E} \left( \sum \limits_{1 \leq x \leq n ,\atop 且 x 号点是 S_{u}^\prime 的重心} x + \sum \limits_{1 \leq y \leq n ,\atop 且 y 号点是 S_{v}^\prime 的重心} y \right)$$

上式中,$E$ 表示树 $S$ 的边集, $(u, v)$ 表示一条连接 $u$ 号点和 $v$ 号点的边。$S_{u}^\prime$ 与 $S_{u}^\prime$ 分别表示树 $S$ 删去边 $(u, v)$ 后, $u$ 号点与 $v$ 号点所在的被分裂出的子树。

小简单觉得作业并不简单,只好向你求助,请你教教他。

输入格式

本题输入包含多组测试数据

第一行一个整数 $T(1\leq T\leq 5)$ 表示数据组数。

接下来依次给出每组输入数据,对于每组数据:

第一行一个整数 $n (1\leq n \leq 3\times 10^5)$ 表示树 $S$ 的大小。

接下来 $n − 1$ 行,每行两个以空格分隔的整数 $u_i , v_i$ ,表示树中的一条边 $u_i,v_i$。

输出格式

共 $T$ 行,每行一个整数,第 $i$ 行的整数表示:第 $i$ 组数据给出的树单独删去每条边后,分裂出的两个子树的重心编号和之和。

样例输入

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

样例解释

对于第一组数据:

删去边 $(1, 2)$ , $1$ 号点所在子树重心编号为 $\{1\}$, $2$ 号点所在子树重心编号为 $\{2, 3\}$。

删去边 $(2, 3)$ , $2$ 号点所在子树重心编号为 $\{2\}$, $3$ 号点所在子树重心编号为 $\{3, 5\}$。

删去边 $(2, 4)$ , $3$ 号点所在子树重心编号为 $\{2, 3\}$, $4$ 号点所在子树重心编号为 $\{4\}$。

删去边 $(3, 5)$ , $3$ 号点所在子树重心编号为 $\{2\}$, $5$ 号点所在子树重心编号为 $\{5\}$。

因此答案为 $1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32$。