题解：CF1987G2 Spinning Round (Hard Version)

· · 题解

upd on 2024.10.6: 修了一张挂掉的图片。

Fun fact：本题被用作了一场 NOIP 模拟赛的 T4。

本文一定程度上参考了 @qiuzx 的 题解。

一些初步的想法是：最终连出来的一定是一棵树；如果除了最大值之外还有其他点只能连自己，则无解。

考虑建出排列对应的大根笛卡尔树。

对于一种不连向自己的连边方案，向左连边就等价于在笛卡尔树上往上跳，直到第一次以右儿子的身份跳上去；向右连边则对应第一次以左儿子的身份跳上去。

\small{ 上图是排列 \{2,1,4,3,5\} 对应的笛卡尔树。} \\ \small{2\ 号点若向右连边，则会连向\ 3\ 号点。}

考虑在笛卡尔树上 dfs，顺带维护这棵新连出的树的直径。

在 dfs 前，我们可以先预处理出只能向右/向左连边的点，稍后特判即可。

类比树的直径的树形 DP 做法，我们尝试在 LCA 处统计贡献。

记 f_{i,0/1/2} 为：从 i 子树内跳出，且最后一步对应 向左/向右/均有 连边，连边数量的最大值（包含跳出去对应的边）。

特别地，对于 f_{i,2}，要求连出来的是两条不交的路径。

假设我们现在在点 x，考虑转移：

  1. 路径不要求含 x：
f_{x, 0} \gets f_{lc_x, 0} \\ f_{x, 1} \gets f_{rc_x, 1} \\ f_{x, 2} \gets f_{lc_x, 0} + f_{rc_x, 1}

注意到如果向左连边并且跳出了左子树，那么一定也跳出了 x 所在子树。其余情况同理。

\small{虚线表示不一定直接相连的点。箭头表示新树上连的边。下同。}
  1. 路径要求包含 x，且 x 向左连边：
f_{x, 0} \gets \max\{f_{lc_x,1},f_{rc_x,0}\} + 1 \\ f_{x, 2} \gets \max\{f_{lc_x,1} + f_{rc_x,1}, f_{rc_x,2}\} + 1

注意到：

这种情况必然不会对 f_{x,1} 产生贡献；

第一个柿子表示从左/右子树跳到了 x，再用一步跳出去；

第二个柿子表示，如果存在一左一右两条跳出 x 子树的路径，由于 x 已经向左跳出，且左子树向右跳只可能跳到 x，故一定是右子树提供了这条向右跳出的路径。

\small{蓝色，紫色箭头表示二选一。下同。}
  1. 路径要求包含 x，且 x 向右连边：

类似 2，不再赘述。

最后来统计答案，记路径两端点的 LCA 为点 x：

  1. 两端点分属 x 的两个子树：
\text{ans} \gets f_{lc_x,1} + f_{rc_x,0}
  1. 两端点来自 x 同一子树内的两条不同路径：

这种情况就不方便在 LCA 处统计了，因为两条边有可能是从子树内很深的点远道而来；我们转而考虑汇合前的最后一次跳跃。

枚举其中一个端点最后一次连边的方向，不妨设在点 y 处向左连边（另一种情况同理）。

\text{ans} \gets \max\{ f_{lc_y,0} + f_{rc_y,0}, f_{lc_y, 2} \} + 1

上式的含义是，要么左子树向左连边，在 y 上方与 x 向左连的边汇合，同时右子树向左连向 y；要么左子树连出一左一右两条边，其中向左的那条边与 y 连的边汇合，向右的那条连向 y。

综上，我们在 O(n) 的时间复杂度内解决了本题。代码实现难度较低。代码。