Cow at Large

题目描述

走投无路的 Bessie 躲进了一个偏远的农场。该农场由 $N$ 个谷仓（$2 \leq N \leq 7 \cdot 10^4$）和 $N-1$ 条连接谷仓的双向隧道组成，因此任意两座谷仓之间都有唯一一条路径。任何只连接一条隧道的谷仓都是一个出口。清晨来临时，Bessie 会在某个谷仓出现，并尝试到达一个出口。

但在 Bessie 出现的瞬间，执法者将能够精确定位她的位置。随后，一些农夫会从不同的出口谷仓出发，试图抓住 Bessie。农夫与 Bessie 的移动速度相同（因此在每个时间步中，每个农夫都可以从一个谷仓移动到相邻的谷仓）。农夫始终知道 Bessie 的位置，Bessie 也始终知道农夫的位置。

如果在任何时刻，有农夫与 Bessie 处于同一座谷仓，或与 Bessie 同时穿过同一条隧道，则农夫抓住了 Bessie。相反，若 Bessie 能在任何农夫抓住她之前严格更早到达某个出口谷仓，则 Bessie 成功逃脱。

Bessie 不确定应当在哪个谷仓出现。对于每一座谷仓，请你帮助 Bessie 确定：如果她在该谷仓出现，并且农夫在出口谷仓之间进行最优分配，那么抓住 Bessie 所需的农夫最少数量是多少。

输入格式

第一行输入 $N$。 接下来 $N-1$ 行每行给出两个整数，范围均为 $1 \ldots N$，描述两座谷仓之间的一条隧道。

输出格式

请输出 $N$ 行，其中第 $i$ 行表示：若 Bessie 在第 $i$ 座谷仓出现，为抓住她所需的农夫最少数量。

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

3
1
3
3
3
1
1

提示

注意：本题的时间限制略高于默认值：C/C++/Pascal 为 4 秒，Java/Python 为 8 秒。

题目鸣谢：Dhruv Rohatgi

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum