問題文

NN 頂点の木があります。i (1iN1)i\ (1 \leq i \leq N - 1) 番目の辺は頂点 AiA_iBiB_i を双方向に結んでいます。

1aN1 \leq a \leq N を満たす全ての整数 aa について次のクエリに答えてください。

  • 頂点 a,c (1cN)a, c\ (1 \leq c \leq N) を端点とする全ての単純パスのうち、パス上に頂点 bb が存在する かつ a<b<ca \lt b \lt c が成立する (b,c)(b, c) の個数を出力する。

制約

  • 3N2×1053 \leq N \leq 2 \times 10^5
  • 1Ai,BiN1 \leq A_i, B_i \leq N
  • 与えられるグラフは木
  • 入力はすべて整数

入力

NN
A1A_1 B1B_1
A2A_2 B2B_2
::
AN1A_{N-1} BN1B_{N-1}

出力

NN 行からなります。i (1iN)i\ (1 \leq i \leq N) 行目には a=ia = i としたときの答えを出力してください。

サンプル

入力1
5
1 2
2 3
3 4
4 5
出力1
6
3
1
0
0
  • a=1a = 1 のとき、条件を満たす (b,c)(b, c)(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)(2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)66 個です。
  • a=2a = 2 のとき、条件を満たす (b,c)(b, c)(3,4),(3,5),(4,5)(3, 4), (3, 5), (4, 5)33 個です。
  • a=3a = 3 のとき、条件を満たす (b,c)(b, c)(4,5)(4, 5)11 個です。
  • a=4a = 4 のとき、条件を満たす (b,c)(b, c) は存在しません。
  • a=5a = 5 のとき、条件を満たす (b,c)(b, c) は存在しません。
入力2
6
1 2
3 1
3 4
3 5
3 6
出力2
3
3
0
0
0
0

提出


Go (1.21)