U119830.公共祖先

给定一棵包含 $n$ 个节点的无根树，节点编号依次为 $1,2,\ldots,n$。

对于每一个节点 $r$，将节点 $r$ 作为整棵树的根。

定义函数 $f_r(i,j)$ 表示在以节点 $r$ 为根的情况下，节点 $i$ 和节点 $j$ 的最近公共祖先节点的编号。

对于每一个可能的根节点 $r$，请计算：

$$S_r=\sum_{i=1}^{n}\sum_{j=1}^{n}f_r(i,j)$$

并依次输出：

$$S_1,S_2,\ldots,S_n$$

注意，本题统计的是所有有序点对 $(i,j)$。也就是说：

• $i<j$ 时需要统计；
• $i>j$ 时需要统计；
• $i=j$ 时也需要统计。

因此，点对 $(i,j)$ 和点对 $(j,i)$ 会被分别计算。

第一行输入一个整数 $n$，表示树的节点数量。

接下来 $n-1$ 行，每行输入两个整数 $u,v$，表示节点 $u$ 和节点 $v$ 之间存在一条无向边。

保证输入的图是一棵树。

输出一行，共包含 $n$ 个整数。

其中第 $r$ 个整数表示以节点 $r$ 为根时：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}f_r(i,j)$$

的值。

相邻两个整数之间用一个空格分隔。

【样例解释 $\# 1$】

给定的树为：

$$1-2-3$$

当节点 $1$ 为根时，节点 $1$、节点 $2$ 和节点 $3$ 作为最近公共祖先出现的次数分别为 $5$、$3$ 和 $1$，因此：

$$S_1=1 \times 5+2 \times 3+3 \times 1=14$$

当节点 $2$ 为根时：

$$S_2=1 \times 1+2 \times 7+3 \times 1=18$$

当节点 $3$ 为根时：

$$S_3=1 \times 1+2 \times 3+3 \times 5=22$$

所以最终输出：

$$14 \quad 18 \quad 22$$

【数据范围】

对于所有数据：

$$1 \leq u,v \leq n \leq 2 \times {10}^5$$

输入保证构成一棵树。

答案保证在有符号 $64$ 位整数范围内。

子任务	分值	限制
1	5	$n=1$
2	10	$1 \leq n \leq 8$
3	15	$1 \leq n \leq 300$
4	15	$1 \leq n \leq 3000$，且树是一条链
5	15	$1 \leq n \leq 5000$
6	15	$1 \leq n \leq 2 \times{10}^5$，且树为菊花图或近似菊花图
7	25	$1 \leq n \leq 2 \times{10}^5$

其中：

• 树为菊花图，指存在一个中心节点与其余所有节点直接相连；
• 树为近似菊花图，指存在一个节点的度数至少为 $\lfloor n/2 \rfloor$。