题目描述

$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$ に到達する際にたどる必要のある最小の辺数です。

输入格式

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

$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)$ を出力せよ。

题目大意

给出 $n$ 个点的树，求出分别以不同的 $i$ 为根时，所有结点深度的和，根节点的深度为 $0$。

3
1 2
2 3

3
2
3

2
1 2

1
1

6
1 6
1 5
1 3
1 4
1 2

5
9
9
9
9
9

提示

制約

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

Sample Explanation 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$、 です。