CF1340D Solution

link

手❤玩❤一❤下，答案大概就是所有点的度数最大值。

下面证明。首先这个肯定是答案的下界，因为度数最大的点至少被经过了它的度数次。

现在考虑构造。对于一棵以 \(u\) 为根的子树，如果我们能证明第一次到 \(u\) 的时间是 \(t\)，

最后一次到 \(u\) 的时间是 \(t-1\) 的话，就可以使得答案是度数最大值（因为这样每遍历一棵子树只会耗费 \(1\) 时间）。

接下来分类讨论，当遍历到点 \(u\)，设 \(d\) 表示 \(u\) 的度数，\(t\) 表示第一次进入 \(u\) 的时间：

• 如果 \(u+d<ans\)，我们直接遍历 \(u\) 这棵子树，在回到 \(u\) 的父亲前把时间调回 \(t-1\) 即可。

• 否则，在遍历到 \(u\) 的某儿子或者中途回到 \(u\) 时时间会达到 \(ans\)。

这时候由于遍历剩下的儿子不会消耗超过 \(d\) 的时间，我们把当前时间减去 \(d\)，最后把时间调回 \(t-1\) 即可。

复杂度线性。