题目背景

原限制 25s & 4096MB，但看起来不需要

题目描述

给定一棵有 $N$ 个点的树，每一个点上有一个人，这些人要开秘密会议。

假设一次秘密会议有 $P$ 个人参加，这 $P$ 个人分别在第 $p_1,p_2,\cdots,p_P$ 个点上。如果点 $k$ 满足下面这个值最小（$d(a,b)$ 为点 $a$ 到点 $b$ 的距离，$k$ 不需要满足 $k \in \{p_1,p_2,\cdots,p_P\}$）：

那么就称第 $k$ 个点为可期待的，这场会议的期待值即为所有点中中可期待点的个数。

对于每个 $j \in [1,N]$，求当会议里有 $j$ 个人的时候，会议的期待值的最大值是多少。

输入格式

第一行一个整数 $N$ 代表树的点数。

接下来 $N-1$ 行每行两个整数 $A_i,B_i$ 代表一条边。

输出格式

$N$ 行每行一个整数，第 $j$ 行代表会议有 $j$ 个人时的答案。

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

提示

样例 1 解释

下文我们称 $\displaystyle\beta_k=\sum\limits_{i=1}^Pd(k,p_i)$。

拿样例 1 中的树举个例子，假设这一次会议参加者为第 $1$ 个点上的人和第 $3$ 个点上的人，则：

• $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$，满足要求的点为 $1,2,3$，该会议的期待值为 $3$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（4 pts）：$N \le 16$。
• Subtask 2（16 pts）：$N \le 4000$。
• Subtask 3（80 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 2 \times 10^5$，$1 \le A_i,B_i \le N$。

说明

翻译自 第２０回日本情報オリンピック　春季トレーニング合宿 Day3 C ビーバーの会合 2 (Meetings 2) 的英文版本。