#abc220f. [abc220_f]Distance Sums 2

[abc220_f]Distance Sums 2

問題文

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

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

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

制約

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

入力

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

NN u1u_1 v1v_1 u2u_2 v2v_2 vdots\\vdots uN1u_{N-1} vN1v_{N-1}

出力

NN 行出力せよ。

ii 行目には sumj=1Ndis(i,j)\\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=3dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3

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

dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3dis(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