問題文
N 頂点の木があります。i (1≤i≤N−1) 番目の辺は頂点 Ai と Bi を双方向に結んでいます。
1≤b≤N を満たす全ての整数 b について次のクエリに答えてください。
- 頂点 a,c (1≤a,c≤N) を端点とする全ての単純パスのうち、パス上に頂点 b が存在する かつ a<b<c が成立する (a,c) の個数を出力する。
制約
- 3≤N≤2×105
- 1≤Ai,Bi≤N
- 与えられるグラフは木
- 入力はすべて整数
入力
出力
N 行からなります。i (1≤i≤N) 行目には b=i としたときの答えを出力してください。
サンプル
- b=1 のとき、条件を満たす (a,c) は存在しません。
- b=2 のとき、条件を満たす (a,c) は (1,3),(1,4),(1,5) の 3 個です。
- b=3 のとき、条件を満たす (a,c) は (1,4),(1,5),(2,4),(2,5) の 4 個です。
- b=4 のとき、条件を満たす (a,c) は (1,5),(2,5),(3,5) の 3 個です。
- b=5 のとき、条件を満たす (a,c) は存在しません。