問題文
N 頂点の木が与えられます。頂点には 1,2,ldots,N の番号がついており、i 番目の辺は頂点 ui,vi を結ぶ無向辺です。
各整数 i,(1leqileqN) に対して、sumj=1Ndis(i,j) を求めてください。
ただし、dis(i,j) は頂点 i から頂点 j に到達する際にたどる必要のある最小の辺数です。
制約
- 2leqNleq2times105
- 1lequi<vileqN
- 与えられるグラフは木
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
u1 v1
u2 v2
vdots
uN−1 vN−1
出力
N 行出力せよ。
i 行目には sumj=1Ndis(i,j) を出力せよ。
入力例 1
出力例 1
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
入力例 3
出力例 3