树上的逆序对

题目描述

给定一棵有 $N$ 个顶点的树 $T$：顶点 $1$、顶点 $2$、……、顶点 $N$。 第 $i$ 条边 $(1\le i\lt N)$ 连接顶点 $u_i$ 和 $v_i$。

对于树 $T$ 中的顶点 $u$，定义 $f(u)$ 如下:

$f(u)$ 定义为满足以下两个条件的顶点对 $(v, w)$ 的数量:

• 顶点 $w$ 包含在连接顶点 $u$ 和 $v$ 的路径中。
• $v \lt w$。

这里，当 $u=w$ 或 $v=w$ 时，也认为顶点 $w$ 包含在连接顶点 $u$ 和 $v$ 的路径中。

请计算 $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)$ 的值，以空格分隔。

样例

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

0 1 3 4 8 9 15

例如，$f(4)=4$。 实际上，对于 $u=4$，满足条件的四对 $(v,w)=(1,2),(1,4),(2,4),(3,4)$。

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

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

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

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

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 \le N \le 2 \times 10^5$
• $1 \le u_i \le N\ (1\le i\le N)$
• $1 \le v_i \le N\ (1\le i\le N)$
• 给定的图是一棵树。
• 所有输入值均为整数。