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 翻译