AT_ttpc2019_m.Inversion Numbers of Tree

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。这棵树的第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

对于这棵树，定义以顶点 $r$ 作为根时的“转倒数”如下：

• 满足如下条件的有序对 $(u, v)\ (u < v)$ 的个数：从顶点 $r$ 到顶点 $u$ 的简单路径的端点或路径上的边包含顶点 $v$。

请你对于所有 $1$ 到 $N$ 的整数 $r$，分别求出以顶点 $r$ 为根时的转倒数。

输入通过标准输入给出，格式如下：

$N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出共 $N$ 行。第 $i$ 行输出以顶点 $i$ 为根时的转倒数。

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 10^{5}$
• $1 \leq A_i, B_i \leq N$
• 给定的图一定是一棵树。

样例解释 1

• 以顶点 $1$ 为根时，转倒数为 $1$，对应的 $(u, v) = (2, 3)$。
• 以顶点 $2$ 为根时，转倒数为 $2$，对应的 $(u, v) = (1, 2),\ (1, 3)$。
• 以顶点 $3$ 为根时，转倒数为 $2$，对应的 $(u, v) = (1, 3),\ (2, 3)$。

由 ChatGPT 4.1 翻译