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)$，用空格分隔。

输入输出样例 #1

输入 #1

7
1 2
2 3
2 4
4 5
4 6
6 7

输出 #1

0 1 3 4 8 9 15

输入输出样例 #2

输入 #2

15
14 9
9 1
1 6
6 12
12 2
2 15
15 4
4 11
11 13
13 3
3 8
8 10
10 7
7 5

输出 #2

36 29 32 29 48 37 45 37 44 42 33 36 35 57 35

输入输出样例 #3

输入 #3

24
7 18
4 2
5 8
5 15
6 5
13 8
4 6
7 11
23 16
6 18
24 16
14 21
20 15
16 18
3 16
11 10
9 11
15 14
12 19
5 1
9 17
5 22
11 19

输出 #3

20 20 41 20 21 20 28 28 43 44 36 63 40 46 34 40 59 28 53 53 66 42 62 63

说明/提示

限制条件

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