自动搬运

查看原文

来自洛谷，原作者为

	irris Good Luck.

搬运于2025-08-24 22:47:11，当前版本为作者最后更新于2021-10-19 22:09:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Preface

$3 - 1 =$ 无望。

令 $1$ 号节点的深度为 $1$。

Solution 1

贪心地考虑，让第 $i$ 个答案 $f(i)$ 由 $f(i - 1)$ 推出。初始值 $f(1) = 0$。

首先 $f(i) \geq f(i - 1) + 1$。通过简单搜索可以得到 $D$ 表示树上 $1\sim n$ 节点的最大深度，那么对于 $i \leq D$，我们从 $1$ 向下依次取一条长度为 $i - 1$ 的不回头的路径，这样取到 $f(i) = i - 1$ 显然不会更劣。若 $i \gt D$，那么由于我们已经贪心地把前 $i$ 个点取完了，所以看样子不能直接 $+1$ 了？

但我们同样知道，可以通过在路径上取一个节点 $u$ 和它的一个未被访问的儿子 $v$，使得原路径由 $\dots \rightarrow u \rightarrow \dots$ 变为 $\dots \rightarrow u \rightarrow v \rightarrow u \rightarrow \dots$，且增加一个访问过的节点。故 $f(i) \leq f(i - 1) + 2$。

那么 $f(i) - f(i - 1)$ 为 $1$ 或 $2$，具体取值只需要比较 $i$ 和 $D$ 的大小关系即可。

Solution 2

如果没有传送操作，那么 $f(i) = 2(i - 1)$，原因是考虑每一条边恰好经过两遍。通过传送操作，我们可以向 $f(i)$ 减少从选择的节点连通块其中一个节点返回根的路径长度，这个长度的最大值即为 $\min(i, D) - 1$。

Postscript

大样例是一条链。