P7565 [JOISC 2021] Beaver Meetings 2 (Day3)

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\}$): $$\sum\limits_{i=1}^P d(k,p_i)$$ 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.

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 $N$ lines, each containing one integer. The $j$-th line should contain the answer when the meeting has $j$ participants.

#### 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](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html), [Day3 C ビーバーの会合 2 (Meetings 2) English version](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day3/meetings2-en.pdf). Translated by ChatGPT 5