F - Distance Sums 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点の木が与えられます。頂点には 1,2,\ldots ,N の番号がついており、i 番目の辺は頂点 u_i,v_i を結ぶ無向辺です。

各整数 i\,(1 \leq i \leq N) に対して、\sum_{j=1}^{N}dis(i,j) を求めてください。

ただし、dis(i,j) は頂点 i から頂点 j に到達する際にたどる必要のある最小の辺数です。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i < v_i \leq N
  • 与えられるグラフは木
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

N 行出力せよ。

i 行目には \sum_{j=1}^{N}dis(i,j) を出力せよ。

入力例 1

3
1 2
2 3

出力例 1

3
2
3

dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3、

dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2、

dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3、

です。

入力例 2

2
1 2

出力例 2

1
1

入力例 3

6
1 6
1 5
1 3
1 4
1 2

出力例 3

5
9
9
9
9
9

Score : 500 points

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1,2,\ldots ,N, and the i-th edge is an undirected edge connecting Vertices u_i and v_i.

For each integer i\,(1 \leq i \leq N), find \sum_{j=1}^{N}dis(i,j).

Here, dis(i,j) denotes the minimum number of edges that must be traversed to go from Vertex i to Vertex j.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i < v_i \leq N
  • The given graph is a tree.
  • All values in input are integers.

Input

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 N lines.

The i-th line should contain \sum_{j=1}^{N}dis(i,j).

Sample Input 1

3
1 2
2 3

Sample Output 1

3
2
3

We have:

dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3,

dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2,

dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3.

Sample Input 2

2
1 2

Sample Output 2

1
1

Sample Input 3

6
1 6
1 5
1 3
1 4
1 2

Sample Output 3

5
9
9
9
9
9