这是一个 SAM 做法。
显然只要求 \(\sum\limits_{1\le i < j \le n}\operatorname{lcp}(i,j)\)。
考虑 \(T_i, T_j\) 在 SAM 上的两条链。显然，这两条链可以被表示为 \(1 \rightarrow P, P \rightarrow x, P \rightarrow y\) 的形式，其中 \(x,y\) 为 \(T_i, T_j\) 在 SAM 上的终止节点。
枚举 \(P\)，算 \(P\) 对答案的贡献。分两步讨论。
-
\(1 \rightarrow P\)，这部分数量就是 \(1 \rightarrow P\) 的路径数量，可以一遍拓扑排序求出。
-
\(P \rightarrow x, y\)，令 \(cnt\) 为 \(P\) 到终止节点的方案数，显然这一部分是 \(C_{cnt}^2\)，\(cnt\) 也可拓扑求出。把两者相乘就是 \(P\) 的贡献。
时间复杂度 \(O(|\sum|n)\)，瓶颈在构造 SAM。