Description

You are given a tree with $N$ vertices. There is one person at each vertex, and they want to hold a secret meeting.

Suppose a secret meeting has $P$ participants, and these $P$ people are located at vertices $p_1, p_2, \cdots, p_P$. If a vertex $k$ minimizes the following value among all vertices (where $d(a,b)$ is the distance between vertices $a$ and $b$, and $k$ does not need to satisfy $k \in \{p_1,p_2,\cdots,p_P\}$):

then vertex $k$ is called expected. The expected value of the meeting is the number of expected vertices in the whole tree.

For each $j \in [1,N]$, find the maximum possible expected value of a meeting with exactly $j$ participants.

Input Format

The first line contains an integer $N$, the number of vertices in the tree.

Each of the next $N-1$ lines contains two integers $A_i, B_i$, representing an edge.

Output Format

Output $N$ lines, each containing one integer. The $j$-th line should contain the answer when the meeting has $j$ participants.

5
1 2
2 3
4 2
3 5

1
4
1
2
1

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

1
5
1
3
1
2
1

Hint

Explanation of Sample 1

Below we denote $\displaystyle\beta_k=\sum\limits_{i=1}^P d(k,p_i)$.

Using the tree in Sample 1 as an example, suppose the participants are the person at vertex $1$ and the person at vertex $3$. Then:

• $P=2$, $p_i=\{1,3\}$.
• $\beta_1=2$.
• $\beta_2=2$.
• $\beta_3=2$.
• $\beta_4=4$.
• $\beta_5=4$.

$\min\limits_{i=1}^5\{\beta_i\}=2$. The vertices that satisfy the condition are $1,2,3$, so the expected value of this meeting is $3$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (4 pts): $N \le 16$.
• Subtask 2 (16 pts): $N \le 4000$.
• Subtask 3 (80 pts): No special constraints.

For $100\%$ of the data, $1 \le N \le 2 \times 10^5$, $1 \le A_i, B_i \le N$.

Notes

Translated from The 20th Japanese Olympiad in Informatics Spring Training Camp, Day3 C ビーバーの会合 2 (Meetings 2) English version.

Translated by ChatGPT 5