题解：P11267 【MX-S5-T1】王国边缘

· · 题解

是题解区目前唯一的 \mathcal{O(n)} 做法！

思路

我们先不管扩展后的串，考虑只将字符在原串中的位置连边，容易发现形成了一个内向基环树森林。而我们要求的，就是求出给定的点在树上走 k 条边后路径的总长加上原来下标对 10^9+7 取模的值。

先考虑一个点如果最后会落在环上怎么做。我们可以提前 \mathcal{O(n)} 处理出每个环外点到环的距离和步数，以及连向环的哪个点；同时环的大小、长度也是可以处理出来的。这样我们就可以将原来的跳跃轨迹砍成三段：走到环 \rightarrow 走完整环 \rightarrow 走部分环。前两段求法比较平凡，对于最后一段，我们可以在环上断边处理出出前缀和，同样可以实现 \mathcal{O(1)} 查询。

再考虑如果没走到环上怎么办。如果依然倍增处理到环距离那么和 \mathcal{O(n\log n)} 的做法相比就没有优势了，因此我们考虑另一种处理到 k 级祖先距离的方法：离线后将询问挂在点上做。实现上，我们反向建一棵外向基环树，从环上点向外 dfs，此时每个深度一定只对应一个点，容易根据当前点的深度差分求出其到 k 级祖先的距离。

那么就做完了！理论复杂度 \mathcal{O(n)}，可能带有较大的常数。

8.2k 的代码

完结撒花~

Welcome to my blog