USACO 2020 December Contest, Silver

Problem 1: 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头病牛。

评分：

• 在测试用例1 - 4中，每个农场都直接连接到农场1（除了农场1本身）。
• 在测试用例5 - 7中，农场$2 \ldots N$每个最多相邻两条道路。
• 在测试用例8 - 15中，没有其他额外限制。

问题作者：Dhruv Rohatgi