G - Tree Inversion Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

頂点 1, 頂点 2,\ldots, 頂点 N の N 頂点からなる木 T が与えられます。 i 番目 (1\leq i\lt N) の辺は頂点 u _ i と頂点 v _ i を結んでいます。

T の頂点 u について f(u) を次のように定めます。

  • f(u)\coloneqq T の頂点 v と頂点 w の組であって、次の 2 つの条件を満たすものの個数
    • 頂点 u と頂点 v を結ぶパス上に頂点 w が含まれる。
    • v\lt w

ただし、「頂点 u と頂点 v を結ぶパス上に頂点 w が含まれる」は、u=w や v=w のときにも成立するとします。

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) の 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) の値は、数列 (14,9,1,6,12,2,15,4,11,13,3,8,10,7,5) の転倒数 57 になります。

入力例 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

Score: 600 points

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