提供一个代码上不一样（？）的做法。
找到询问集合中，深度最大的点 \(mx\)。如果都最后一个点了，还拐到别的分支，显然毫无意义，所以 \((1,mx)\) 的路径是最优的。
那就好做了。\(\operatorname{lca}(mx,q_i)\) 显然在 \((1,mx)\) 里，所以只需检查 \(\forall\operatorname{dist}(q_i, \operatorname(mx, q_i))\le 1\) 即可。
代码，时间复杂度 \(O(k\log n)\)。
CF1328E 题解
发布时间 2023-07-10 11:14:11作者: liangbowen