AT_abc337_g.[ABC337G] Tree Inversion

给定一棵包含 $N$ 个顶点的树 $T$，顶点编号为 $1, 2, \ldots, N$。第 $i$ 条边（$1 \leq i < N$）连接顶点 $u_i$ 和顶点 $v_i$。

对于树 $T$ 的每个顶点 $u$，定义 $f(u)$ 如下：

• $f(u)$ 等于满足以下两个条件的顶点对 $(v, w)$ 的个数：
  1. 在连接顶点 $u$ 和顶点 $v$ 的路径上包含顶点 $w$。
  2. $v < w$

其中，“在连接顶点 $u$ 和顶点 $v$ 的路径上包含顶点 $w$”在 $u = w$ 或 $v = w$ 时也成立。

请计算 $f(1), f(2), \ldots, f(N)$ 的值，并按顺序输出。

输入以以下格式从标准输入读入。

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

请按顺序输出 $f(1), f(2), \ldots, f(N)$，用空格分隔。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i \leq N\ (1 \leq i < N)$
• $1 \leq v_i \leq N\ (1 \leq i < N)$
• 给定的图是一棵树
• 所有输入均为整数

样例解释 1

给定的树如下图所示。

例如，$f(4) = 4$。实际上，对于 $u = 4$，有 $4$ 组 $(v, w)$ 满足条件，分别为 $(1,2), (1,4), (2,4), (3,4)$。

样例解释 2

给定的树如下图所示。

$f(14)$ 的值等于数列 $(14,9,1,6,12,2,15,4,11,13,3,8,10,7,5)$ 的逆序对数 $57$。

由 ChatGPT 4.1 翻译