题解只给了code，能不能解释一下这到底是在做什么以及这样做为什么是对的？

link

翻译如下：（机翻）

---

首先，考虑解决方案而不考虑计算量。

考虑一个具有$N$个顶点的图形。当$S_i=S_j$时，在顶点$i$和$j$之间连接一条蓝色边；当$S_i\neq S_j$时，在顶点$i$和$j$之间连接一条红色边。

首先，对于每个$i$，根据$(S_{i-A_i},S_{i-A_i+1},\dots,S_{i+A_i})$构成回文串的条件，添加蓝色边$(i-A_i,i+A_i), (i-A_i+1,i+A_i-1), \dots, (i-1,i+1)$。

接下来，对于每个$i$，如果$2\leq i-A_i,i+A_i\leq N-1$，则需要满足$(S_{i-A_i-1},S_{i-A_i+1},\dots,S_{i+A_i+1})$不构成回文串的条件，即$S_{i-A_i-1}\neq S_{i+A_i+1}$。因此，在顶点$i-A_i-1$和$i+A_i+1$之间添加红色边$(i-A_i-1,i+A_i+1)$。

蓝色边连接的连通分量中的顶点必须取相同的值。因此，缩减蓝色边连接的连通分量。然后，在每个连通分量中，按照红色边两端的顶点取不同的值，即可求得解。

缩减连通分量后，若存在由红色边构成的自环，则无法给连通分量赋值满足条件的$S$。

若不存在由红色边构成的自环，则从包含较小编号顶点的连通分量开始，贪心地依次给尚未使用的较小值赋予相邻连通分量，直到所有值被分配为止。

以上解法的问题在于蓝色边的最大数量为$O(N^2)$。因此，必须在保持蓝色边的连通性的前提下，减少必须连接的蓝色边的数量。

通过 Manacher 算法实现加速

通过应用Manacher算法，可以将蓝色边的数量减少至$O(N)$。Manacher算法是一种在$O(N)$时间内计算给定字符串的以每个索引为中心的最大回文子串长度的算法。

Manacher算法的核心思想是“利用已经计算过的信息，省略已知构成回文的部分的计算”。有关算法的详细解释请参见以下文献：

• 中文：字符串的头好感觉的线性算法们2
• 英文：Manacher’s Algorithm - Finding all sub-palindromes in $O(N)$

通过应用Manacher算法，当存在满足条件的$S$时，可以通过以下伪代码正确地构建蓝色边。

在此，注意$A$的索引和顶点编号从0开始计数。此外，函数unite(u, v)用于在顶点$u,v$之间添加蓝色边。

分析该算法的时间复杂度。乍看之下，由于存在双重循环，似乎为$O(N^2)$。实际上，我们将证明它实际上是$O(N)$的。

首先，分析第3行的while循环while j < A[i] + 1的执行次数。注意$i+j$的值，

• 考虑第10行和第11行，此时$i+j$保持不变
• $i+j$只在第5行发生变化，每次变化递增1
• 根据第3行的while循环条件，有$i+j \leq i+A[i] \leq i+(N-i-1) < N$

因此，第3行的while循环最多执行大约$N$次。

其次，分析第8行的while循环while i - k >= 0 and k + A[i - k] + 1 < j的执行次数。考虑$i$的值，

• $k$是第8行while循环在该步骤中执行的次数
• 由于$i$是$k$的总和，因此整个算法中第8行while循环执行的次数
• 根据第2行while循环条件，有$i < N$

因此，第8行的while循环最多执行大约$N$次。

综上所述，可以确认该算法在$O(N)$时间内运行。

以上算法实际上是在“当存在满足条件的$S$时”条件下运行的。因此，必须检查得到的$S$实际上是否满足条件。通过再次使用Manacher算法，可以在$O(N)$时间内进行此检查。