题链
可以把\(\sum\)拆开，只需要计算\(\sum_{i<j}LCP(suf[i],suf[j])\)
这显然是后缀数组裸题，所以我们采用后缀自动机来解决
后缀的前缀很难看，不妨翻转字符串，求前缀的后缀，应用parent tree
发现任意两个节点\(i,j\)的最长后缀为Len(LCA(i,j)),对每个节点求出子树中的点对，用DP统计

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e6+5;
int n,tot,lst,g[N],q[N],d[N];
ll ans;
char s[N];
struct A{
	int len,fa,c[30];
}dian[N];

inline void SAM(int ch) {
	int np=++tot,p=lst; lst=np;
	dian[np].len=dian[p].len+1; g[np]=1;
	for(;p&&!dian[p].c[ch];p=dian[p].fa) dian[p].c[ch]=np;
	if(!p) dian[np].fa=1;
		else {
			int q=dian[p].c[ch];
			if(dian[q].len==dian[p].len+1) dian[np].fa=q;
				else {
					int nq=++tot; dian[nq]=dian[q];
					dian[nq].len=dian[p].len+1;
					dian[q].fa=dian[np].fa=nq;
					for(;p&&dian[p].c[ch]==q;p=dian[p].fa) dian[p].c[ch]=nq;
				}
		}
}

int main(){
	scanf("%s",s+1); n=strlen(s+1);
	for(int i=1;i<=n/2;i++) swap(s[i],s[n-i+1]); 
	ans=(ll)(n-1)*n*(n+1)>>1;
	tot=lst=1;
	for(int i=1;i<=n;i++) SAM(s[i]-'a');
	int l=1,r=0;
	for(int i=1;i<=tot;i++) {
		d[dian[i].fa]++;
	}
	for(int i=1;i<=tot;i++) {
		if(!d[i]) q[++r]=i;
	}
	while(l<=r) {
		int u=q[l];l++;
		d[dian[u].fa]--;
		if(!d[dian[u].fa]) q[++r]=dian[u].fa;
		g[dian[u].fa]+=g[u];
	}
	for(int i=2;i<=tot;i++) {
		ans-=(ll)g[i]*(g[i]-1)*(dian[i].len-dian[dian[i].fa].len);
	}
	printf("%lld\n",ans);
	return 0;
}