[JOISC 2021 Day3] ビーバーの会合 2

原限制 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\}$）： $$\sum\limits_{i=1}^Pd(k,p_i)$$ 那么就称第 $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$。 #### 说明 翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day3 C ビーバーの会合 2 (Meetings 2) 的英文版本](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day3/meetings2-en.pdf)。