题解：P9664 [ICPC2021 Macao R] LCS Spanning Tree

· · 题解

\textbf{P9664}
  • 给定 n 个字符串 s_1,s_2,\ldots,s_n，构造 n 个点的无向完全图 G，边 i,j 的边权是 \operatorname{LCS}(s_i,s_j)，其中 \operatorname{LCS} 指最长公共子串。
  • 求 G 的最大生成树边权和。

后缀数组做这题应该是最简单的吧。

回忆一下我们是怎么用 SA 求两串 \operatorname{LCS} 的，我们是直接拼起来，然后枚举 rk 相邻的归属串不同的两个后缀计算 \operatorname{LCP} 后取 \max。

把所有 s_i 拼起来用不同的分隔符隔开，我们有结论有用的边只有 (sa_i,sa_{i+1}) 这 \mathcal O(\sum |s_i|) 条。考虑一条边 (sa_i,sa_{i+k}) \; (k \ge 2)，其边权等于 (sa_i,sa_{i+1}),\ldots,(sa_{i+k-1},sa_{i+k}) 边权的最小值，我们在 Kruskal 合并的过程中一定会先把中间的边都考虑完，而此时 sa_i,sa_{i+k} 必然已经连通，因此 (sa_i,sa_{i+k}) 这条边没有用。

令 m = \sum |s_i|，时间复杂度 \mathcal O(m \log m)。