Cowntagion

题目描述

农夫约翰和他的同伴们一直在不停地努力，控制可怕的牛类疾病 COWVID-19 在他们农场间的传播。 他们共同管理着 $N$ 个农场（$1 \leq N \leq 10^5$），方便起见编号为 $1 \ldots N$。这些农场通过 $N-1$ 条道路相连，使得任意农场都可以通过若干条道路从农场 1 到达。 不幸的是，农场 1 中的一头牛刚刚检测出 COWVID-19 阳性。该农场的其他牛以及其他任何农场的牛目前都还没有感染。 然而，考虑到该疾病的传染性，农夫约翰预计在之后的每一天都会发生下面两种不利事件中的恰好一种： (1) 在某一个农场发生一次“超级传播”事件，使得该农场中感染 COWVID-19 的牛的数量翻倍；或 (2) 一头感染 COWVID-19 的牛沿着一条道路从一个农场移动到相邻的另一个农场。 农夫约翰担心疫情蔓延得有多快。请你帮助他，确定最少需要多少天后，才有可能出现每个农场中至少有一头牛感染的情况。

输入格式

第一行包含一个整数 $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 头患病的牛。 SCORING: 在测试点 1-4 中，每个农场都与农场 1 直接相连（不包括农场 $1$ 本身）。 在测试点 5-7 中，农场 $2\ldots N$ 中每个农场的相邻道路数最多为两条。 在测试点 8-15 中，没有额外限制。 题目来源：Dhruv Rohatgi

标签: USACO|2020|Silver

来源

USACO|2020|Silver