令 $h_u$ 表示 $u$ 到其子树中某个叶子的最远距离，$siz_u$ 表示 $u$ 子树的点数。对于这个问题如果我们要求 A,B 最终都回到 $1$，那么是非常简单的，可以设计 $dp_u$ 表示 A,B 都在 $u$，子树中均未被染色，访问 $u$ 子树所有点的最小操作次数，使得 A,B 最终都回到 $u$ 的最小操作次数，对于每个子树 $v$，如果 $h_v\leq k-1$ 那么可以让 A 在 $u$ 不动，让 B 下去走一个欧拉环游序，走到最远叶子时仍然满足 $\text{dis}(A,B)\leq k$，贡献是 $2siz_u$；否则是 $4+dp_v$（考虑 A,B 对于边 $(u,v)$ 往返）。
然而答案显然可以做到更小，因为我们可以选取一个子树下去之后再也不上来，或者选两个子树，A,B 各完成一个；我们可以设计 $f_u$ 表示 A,B 当前都在 $u$，$u$ 子树之外的所有点都已经完成的最小代价，可以从上往下求。然后有两种情况：
- 钦定其中一个子树 $v$ 使得 $h_v \leq k-1$。另外的子树都已经被访问完了。A 停留在 $u$，B 下去走子树 $v$，最终停留在 $v$ 子树最远的叶子。
- 钦定两个子树 $x,y$ 使得 $h_x,h_y\leq k-1$。另外的子树都已经被访问完了，A 先走完子树 $x$，B 再走完子树 $y$。显然 A 不能走到 $y$ 子树，反之亦然，因而要求 $h_x,h_y\leq k-1$，这样做是因为如果不这样会形成 $dp$ 代表的子问题。问题是你无法保证 $y$ 走完后 $\text{dis}(A,B)\leq k$，因此还需要计算 $\max(0,h_x+h_y+2-k)$ 的额外贡献。直接枚举 $x,y$ 是 $n^2$ 的，但是对于所有子树按照 $h$ 排序之后可以双指针做。
时间复杂度 $\mathcal O(n\log n)$。
鄂公网安备 42010202000505 号