103376: [Atcoder]ABC337 G - Tree Inversion

Problem Statement

You are given a tree $T$ with $N$ vertices: vertex $1$, vertex $2$, $\ldots$, vertex $N$. The $i$-th edge $(1\leq i\lt N)$ connects vertices $u_i$ and $v_i$.

For a vertex $u$ in $T$, define $f(u)$ as follows:

• $f(u)\coloneqq$ The number of pairs of vertices $v$ and $w$ in $T$ that satisfy the following two conditions:
  • Vertex $w$ is contained in the path connecting vertices $u$ and $v$.
  • $v\lt w$.

Here, vertex $w$ is contained in the path connecting vertices $u$ and $v$ also when $u=w$ or $v=w$.

Find the values of $f(1),f(2),\ldots,f(N)$.

Constraints

• $2\leq N\leq2\times10^5$
• $1\leq u_i\leq N\ (1\leq i\leq N)$
• $1\leq v_i\leq N\ (1\leq i\leq N)$
• The given graph is a tree.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the values of $f(1),f(2),\ldots,f(N)$ in this order, separated by spaces.

Sample Input 1

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

Sample Output 1

0 1 3 4 8 9 15

The given tree is as follows:

For example, $f(4)=4$. Indeed, for $u=4$, four pairs $(v,w)=(1,2),(1,4),(2,4),(3,4)$ satisfy the conditions.

Sample Input 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

Sample Output 2

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

The given tree is as follows:

The value of $f(14)$ is $57$, which is the inversion number of the sequence $(14,9,1,6,12,2,15,4,11,13,3,8,10,7,5)$.

Sample Input 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

Sample Output 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

问题描述

你被给定一个有$N$个顶点的树：顶点$1$，顶点$2$，$\ldots$，顶点$N$。 第$i$条边（$1\leq i\lt N$）连接顶点$u_i$和$v_i$。

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

• $f(u)\coloneqq$在树中满足以下两个条件的顶点$v$和$w$的数量：
  • 顶点$w$包含在连接顶点$u$和$v$的路径中。
  • $v\lt w$。

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

找到$f(1),f(2),\ldots,f(N)$的值。

约束

• $2\leq N\leq2\times10^5$
• $1\leq u_i\leq N\ (1\leq i\leq N)$
• $1\leq v_i\leq N\ (1\leq i\leq 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

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

样例输出 1

0 1 3 4 8 9 15

给定的树如下：

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

样例输入 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

给定的树如下：

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

样例输入 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