CF1062E Company

· · 题解

cnblogs

来一个小丑做法，不用观察太多性质，符合像我这样 DS 学魔怔的蒟蒻体质，目前题解区没有看到，麻烦管理再单独开一下题解通道。

洛谷 CF

  • 给出一棵 n 个点的有根树以及 q 次询问，每次询问给出 l,r，你要去掉 [l,r] 中的一个点，使得剩余点 \text{LCA} 的深度最大。

我们考虑怎样的点可以成为 \text{LCA}，显然它一定在 l 到根的路径、r 到根的路径的并集中。因为只能删去一个点，所以最终的 \text{LCA} 一定是 l,r 中至少一个点的祖先。

称点 u 向上走 k 条边到达的点为 u 的 k 级祖先，不难发现答案具有单调性。即，若 u 的 k 级祖先能成为公共祖先，则 u 的 k+1 级祖先也可以成为公共祖先。

考虑对两条根链分别二分出最近的祖先。一个点 u 能成为剩余点的祖先，当且仅当其子树中 [l,r] 内的点个数 \ge r-l。若个数 =r-l+1，则删去任意一个点。若个数 =r-l，则删去那个缺失的点。否则，我若任意删除 [l,r] 内的一个点，剩余点中都存在一个点，使得 u 不是它的祖先。

所以判定可以转化为子树数点，用 dfs 序拍平上主席树维护即可。

二分出来两个级别后，选择深度较大的 k 级祖先即可。

但是这题还要输出删除哪个点。我们记选择的祖先为 anc。若 anc 子树内包含了 [l,r] 的所有点，则任意输出一个即可。否则考虑找到那个没出现的点。

这个问题等价于在区间内找到给定值域内最小的未出现的数。设它为 x，则 x 一定是一个最小的数，满足 [l,x] 内的数没有全部出现过。同样具有单调性，可以二分再使用主席树判定，复杂度瓶颈不变，但是常数太大了，会被卡。

所以我们在主席树上带边界地二分，这样单次找数的时间复杂度为 \mathcal{O}(\log n)。瓶颈的常数会除以 2。

但是这样你还是会在最后一个点被卡。

我们发现最后一个点是链，因此直接特判链的情况即可。

由于 CF 特殊的构造链的方式（点 i 的父亲是 i-1），可以方便我们的判断，以及回答的时候直接输出两个 l 即可。

若链构造得更加一般，就 dfs 判定每个点是否只有一个儿子，回答的时候删去深度最小的点，\text{LCA} 的深度为深度次小的点，用一棵线段树维护。笔者没有实现过，这部分有错还希望能够提出来。

然后就可以配合卡常通过此题。时间复杂度为 \mathcal{O}(n\log ^2 n)，空间复杂度为 \mathcal{O}(n\log n)。

提交记录（含代码）