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