F - Scapus 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

頂点に 1 から N までの番号が付いた N 頂点の木が与えられます。 i 番目 (1 \le i \le N - 1) の辺は頂点 A_i と頂点 B_i を結んでいます。

この木のパスについて、パスから最も遠い頂点までの距離をスコアとします。 ただし、パスからの距離とは、パスの頂点との距離の最小値を表します。

スコアが最小になるようなパスを良いパスと呼びます。

k = 1,2,\ldots, N それぞれについて、頂点数が k であるような良いパスの個数を求めて下さい。 ただし、パスは頂点集合が異なるときにのみ区別します。

制約

  • 2 \le N \le 2 \times 10^5
  • 1 \le A_i < B_i \le N (1 \le i \le N - 1)
  • 与えられるグラフは木
  • 入力される値は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}

出力

N 行出力せよ。

k 行目には、頂点数が k であるような良いパスの個数を出力せよ。

入力例 1

5
1 2
2 3
2 4
3 5

出力例 1

0
1
3
2
0

スコアの最小値は 1 です。

良いパスは以下の 6 つです。

  • 頂点 2 と頂点 3 を結ぶ頂点数 2 のパス
  • 頂点 1 と頂点 3 を結ぶ頂点数 3 のパス
  • 頂点 2 と頂点 5 を結ぶ頂点数 3 のパス
  • 頂点 3 と頂点 4 を結ぶ頂点数 3 のパス
  • 頂点 1 と頂点 5 を結ぶ頂点数 4 のパス
  • 頂点 4 と頂点 5 を結ぶ頂点数 4 のパス

入力例 2

8
1 2
2 3
2 4
3 5
5 6
3 7
7 8

出力例 2

1
3
7
8
5
0
0
0

入力例 3

5
1 2
2 3
3 4
4 5

出力例 3

0
0
0
0
1

Score : 700 points

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge (1 \le i \le N - 1) connects vertices A_i and B_i. For a path in this tree, define the score of the path as the distance from the path to the farthest vertex. Here, the distance from a path is defined as the minimum distance to a vertex on the path.

A path with the minimum score is called a good path.

For each k = 1, 2, \ldots, N, find the number of good paths with exactly k vertices. Paths are distinguished only if their vertex sets differ.

Constraints

  • 2 \le N \le 2 \times 10^5
  • 1 \le A_i < B_i \le N (1 \le i \le N - 1)
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}

Output

Output N lines.

The k-th line should contain the number of good paths with exactly k vertices.

Sample Input 1

5
1 2
2 3
2 4
3 5

Sample Output 1

0
1
3
2
0

The minimum score is 1.

The good paths are the following six paths.

  • The path with two vertices connecting vertices 2 and 3
  • The path with three vertices connecting vertices 1 and 3
  • The path with three vertices connecting vertices 2 and 5
  • The path with three vertices connecting vertices 3 and 4
  • The path with four vertices connecting vertices 1 and 5
  • The path with four vertices connecting vertices 4 and 5

Sample Input 2

8
1 2
2 3
2 4
3 5
5 6
3 7
7 8

Sample Output 2

1
3
7
8
5
0
0
0

Sample Input 3

5
1 2
2 3
3 4
4 5

Sample Output 3

0
0
0
0
1