护林员¶
- 参考时间限制：0.5 秒（评测环境与性能）。
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 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¶
输入¶
6
1 2
1 3
1 4
1 5
5 6
输出¶
4
2
3
4
5
解释¶
第一天沿 \(1\to5\to6\to5\to1\) 行走，检查顶点 \(5,6\) . 其余三天各检查顶点 \(2,3,4\) 中的一个。
样例 2¶
输入¶
4
1 2
2 3
3 4
输出¶
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% | 无额外条件 |