問題文


頂点の木があります。 番目の辺は頂点 を双方向に結んでいます。

を満たす全ての整数 について次のクエリに答えてください。

  • 頂点 を端点とする全ての単純パスのうち、パス上に頂点 が存在する かつ が成立する の個数を出力する。

制約


  • 与えられるグラフは木
  • 入力はすべて整数

入力






出力


行からなります。 行目には としたときの答えを出力してください。

サンプル


入力1
5
1 2
2 3
3 4
4 5
出力1
0
3
4
3
0
  • のとき、条件を満たす は存在しません。
  • のとき、条件を満たす 個です。
  • のとき、条件を満たす 個です。
  • のとき、条件を満たす 個です。
  • のとき、条件を満たす は存在しません。
入力2
6
1 2
3 1
3 4
3 5
3 6
出力2
0
0
6
0
0
0

Submit


Go (1.14)