P9304 Solution

irris · 2021-10-19 22:09:28 · 题解

3 - 1 = 无望

认为根结点的深度为 1，记 d 表示树上某个结点的最大深度。

如果没有传送操作，那么 f(i) = 2(i - 1)，原因是过程类似 DFS，每一条边恰好被经过两遍。

传送操作允许我们选择访问点集中某个结点 x，在离开 x 时，直接传送到根并不再移动（总可以通过交换移动顺序达成如此）。这省去的距离等于 x 的深度减 1，故而只需计算 x 深度的最大值，显然是 \min(i, d)。

大样例是一条链。