[AdditionalFile3495.zip](file://AdditionalFile3495.zip?type=additional_file)

#3495. 「JOISC 2021 Day3」聚会 2

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 JOISC 2021 Day3 T3「ビーバーの会合 2 / Meetings 2」

河狸们居住在 $N$ 个岛上。这些岛从 $1$ 到 $N$ 编号，并通过 $N-1$ 座双向连接的桥连通。这些桥的编号为 $1$ 到 $N-1$。桥 $i$ 连接岛 $A_i$ 和 $B_i$。通过桥可以在任意岛之间穿梭。每个岛上有一只河狸定居。

有时，在某些岛上居住的河狸们要聚集到一个岛上开会。当一场会议的出席者确定了之后，满足以下条件的一个岛就被选为开会地址：

• 参会者为了到达这个岛开会所需要经过桥的数量的总和是最小的。

这里，当会议的出席者确定时，每位出席者都会经过最少数量的桥前往开会所在岛。

会议出席者都希望会议的候选岛很多。当一场会议的出席者确定时，这场会议的期待值等于满足以上条件的岛的个数。对于每个从 $1$ 到 $N$ 的整数 $j$（包括两端），你想知道当有 $j$ 位河狸参会时，这场会议的最大期待值是多少。

给定这些岛的信息，写一个程序计算对每一个参会河狸数，这场会议的最大期待值是多少。

输入格式

从标准输入读入以下内容。

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$，用一个空格隔开。

输出格式

输出 $N$ 行到标准输出。第 $j\ (1\le j\le N)$ 行输出当参会者有 $j$ 位时，最大的期待值是多少。

样例 1

输入

5
1 2
2 3
4 2
3 5

输出

1
4
1
2
1

例如，我们考虑居住在岛 $1$ 和岛 $3$ 的河狸参加的会议。对于每一个岛，他们要经过的桥的数量之和按如下方法计算。

• 如果他们在岛 $1$ 聚集，住在岛 $1$ 的河狸不需要过桥，住在岛 $3$ 的河狸需要经过 $2$ 座桥，总和为 $2$；
• 如果他们在岛 $2$ 聚集，他们经过桥的数量总和为 $2$；
• 如果他们在岛 $3$ 聚集，他们经过桥的数量总和为 $2$；
• 如果他们在岛 $4$ 聚集，他们经过桥的数量总和为 $4$；
• 如果他们在岛 $5$ 聚集，他们经过桥的数量总和为 $4$；

所以候选岛为岛 $1,2,3$。因此，这次会议的期待值为 $3$。

样例 2

输入

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

输出

1
5
1
3
1
2
1

数据范围与提示

对于所有数据，保证：

• $1\le N\le 2\times 10^5$
• $1\le A_i,B_i\le N\ (1\le i\le N-1)$
• $A_i\neq B_i\ (1\le i\le N-1)$
• 保证可以通过桥从一个岛前往任意一个岛

详细子任务附加条件及分值如下表：

子任务编号	附加条件	分值
$1$	$N\le 16$	$4$
$2$	$N\le 4\ 000$	$16$
$3$	无附加限制	$80$

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

题目描述

给定一棵有 $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$ 个人时的答案。

输入输出样例 #1

输入 #1

5
1 2
2 3
4 2
3 5

输出 #1

1
4
1
2
1

输入输出样例 #2

输入 #2

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

输出 #2

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) 的英文版本。