# 护林员

- 参考时间限制：**0.5 秒**（[评测环境与性能](../../../docs/评测环境与性能.md)）。
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整。
- 内存限制：512 MB

## 背景故事

森林里的步道连成一棵树，入口处设有护林站，其余地点都是需要巡查的检查点。每个检查点完成一次检查即可。

护林员每天从护林站出发，沿步道巡查后返回。一旦回到护林站，当天的巡查就结束了；同一地点每天最多经过两次。

他希望用最少的天数检查完所有检查点，同时让每一天结束时累计完成检查的地点尽可能多。请帮他安排巡查进度。

(本故事由GPT-6重写)

## 形式化问题描述

给定一棵以顶点 $1$ 为根、共有 $n$ 个顶点的无向树。顶点 $2,\ldots,n$ 各有一个检查点，每个检查点只需完成一次巡查任务。每天选择一条从顶点 $1$ 出发、最终返回顶点 $1$ 的树上行走路线；除起点和终点外，路线不能经过顶点 $1$ ，且每个顶点在当天至多被访问两次。在经过一个顶点时，可完成该顶点尚未完成的任务。

访问次数按路线的顶点序列计数，包括出发和返回时的顶点 $1$ . 某天已经检查过的顶点，在其他天仍可经过。

首先求完成全部任务所需的最少天数 $D$ . 随后对每个 $k=1,\ldots,D$ ，求所有能在 $D$ 天内完成全部任务的行程安排中，前 $k$ 天结束时已完成任务数的最大值。可以证明，存在同一个行程安排同时达到这些最大值；只需输出数值，无需输出路线。

## 输入格式

第一行一个整数 $n$ . 接下来 $n-1$ 行，每行两个整数 $u,v$ ，表示树的一条边。

## 输出格式

第一行输出最少天数 $D$ . 接下来 $D$ 行，第 $k$ 行输出前 $k$ 天结束时最多能累计完成的任务数。

## 样例 1

### 输入

```text
6
1 2
1 3
1 4
1 5
5 6
```

### 输出

```text
4
2
3
4
5
```

### 解释

第一天沿 $1\to5\to6\to5\to1$ 行走，检查顶点 $5,6$ . 其余三天各检查顶点 $2,3,4$ 中的一个。

## 样例 2

### 输入

```text
4
1 2
2 3
3 4
```

### 输出

```text
1
3
```

## 数据范围与保证

- $2\le n\le 1\,000\,000$ .
- 输入的 $n-1$ 条边构成一棵无向树，$1\le u,v\le n$ .

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 30% | $n\le 10$ |
| 30% | $n\le 5\,000$ |
| 40% | 无额外条件 |