3517. [USACO20Dec Silver]Cowntagion

【题目描述】

Farmer John 和他的农民团队为了控制牛传染病 COWVID-19 在他们农场间的传播而夜以继日地工作。

他们共同监控着 $N$ 个农场（$1 \leq N \leq 10^5$），编号为 $1 \ldots N$。农场间由 $N-1$ 条道路连接，使得每个农场都可以从农场 1 出发经过一些道路到达。

很不幸，农场 1 中的一头奶牛的 COWVID-19 检测呈阳性。暂时这个农场的其他奶牛以及其他农场的所有奶牛都还没有染上疾病。然而，根据这个疾病通过接触传播的特性，Farmer John 推测每一天都会有以下不利的事件之一发生：

(1) 在一个农场内，「超级传播者」导致该农场感染 COWVID-19 的奶牛数量翻倍；或者

(2) 一头感染 COWVID-19 的奶牛从一个农场沿道路去往了一个相邻的农场。

Farmer John 担心疫情会很快爆发。请帮助 Farmer John 求出每个农场内均有至少一头奶牛感染疾病所需经过的最小天数。

【输入格式】

输入的第一行包含一个整数 $N$。以下 $N-1$ 行每行包含两个空格分隔的整数 $a$ 和 $b$，表示一条农场 $a$ 与 $b$ 之间的道路。$a$ 和 $b$ 均在 $1\ldots N$ 范围内。

【输出格式】

输出疫情爆发至所有农场所需经过的最小天数。

【样例输入】

4
1 2
1 3
1 4

【样例输出】

5

【样例说明】

该样例对应的一个可能的事件序列如下：

农场 1 内染病的奶牛数量翻倍再翻倍，使得两天后农场 1 内有 4 头染病的奶牛。

在此后 3 天，分别有一头染病的奶牛从农场 1 去往农场 2、3 和 4。

5 天过后每个农场均有至少 1 头染病的奶牛。

【数据规模与约定】

对于$ 27\% $的测试数据(测试点$ 1\sim4 $)，每个农场均直接与农场 1 相连（除农场 $1$ 外）。

另有$ 20\% $的测试数据(测试点$ 5\sim7 $)，农场 $2\ldots N$ 均至多与两条道路相连。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月月赛 Silver 组