5093：文件传递
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 文件传递
## 题目描述
某个古老的王国有 $N$ 个城市，编号为 $1 \ldots N$ 。这些城市通过 $N-1$ 条双向道路连接，形成一个树形结构，其中 $1$ 号城市是首都。每个城市都可以从 $1$ 号城市出发通过若干条双向道路到达。
某天， $1$ 号城市准备将一条重要的公告文件中的信息，传递到王国中的的所有城市。
王国传递公告文件信息的过程，有一定的特殊性。具体来说，**每天** $N$ 个城市中，**只会有一个**城市进行文件信息的传递工作，这个城市会做如下两种操作**其中之一**的工作。
- **抄写文件**：如果当前城市中已有公告文件，该城市会将当前城市中公告文件的数量通过抄写翻倍。
- **文件传输**：如果当前城市中有公告文件，该城市可以选择将其中**一份**公告文件从当前城市，沿双向道路传送到其他城市，该城市中公告文件的数量会少一份。
请帮助王国计算，每个城市都能获得**至少一份**公告文件，所需的**最少天数**。
## 输入格式
输入的第一行包含一个整数 $N$ ，表示城市的数量。
接下来的 $N-1$ 行，每行包含两个整数 $U_i$ 和 $V_i$ ，表示服务器 $U_i$ 和 $V_i$ 之间有一条双向道路。
## 输出格式
输出一个整数，表示每个城市都能获得至少一份公告文件，所需的最少天数。
## 样例
### 样例输入 1
```text
3
1 2
1 3
```
### 样例输出 1
```text
4
```
### 样例输入 2
```text
5
1 2
2 3
3 4
4 5
```
### 样例输出 2
```text
8
```
### 样例输入 3
```text
12
1 2
1 3
2 4
2 5
3 6
3 7
7 8
7 9
8 10
10 11
10 12
```
### 样例输出 3
```text
22
```
## 说明/提示
样例 $1$ 说明
一个可能的传递方式如下：
- 第 $1$ 天： $1$ 号城市将公告文件数量抄写翻倍，得到 $2$ 份公告文件。
- 第 $2$ 天： $1$ 号城市再次将公告文件数量抄写翻倍，得到 $4$ 份公告文件。
- 第 $3$ 天： $1$ 号城市将公告文件，传递到 $2$ 号城市。
- 第 $4$ 天： $1$ 号城市将公告文件，传递到 $3$ 号城市。
经过 $4$ 天后，每个城市都能获得至少一份公告文件。
数据范围
对于 $25\%$ 的测试数据，满足 $2 \sim N$ 的每个城市直接与 $1$ 号城市相连。
对于另外 $20\%$ 的数据，满足 $2 \sim N$ 的每个城市，与该城市连接的双向道路最多有 $2$ 条。
对于 $100\%$ 的数据，满足 $1 \leq N \leq 10^5$ ， $1 \le U_i, V_i \leq N$ ， $U_i \neq V_i$ 。
---
**题目来源：** 25年3月-C组（大咖）