题解：首先所有后缀都在最后一个np节点，然后他们都是从1号点出发沿一些字符边到达这个点的，所以下文称1号点为根节点，我们思考一下什么时候会产生lcp，显然是当他们从根节点开始一直跳相同节点的时候，所以思路就是先找出每个节点被几个后缀经过，这显然把边反转倒着找就可以了，然后他会被出现次数sz个串经过。
出现次数等于parent树子树中np类节点的个数，这跑个dfs就好了，一个相同前缀产生的贡献是sz*(sz-1)/2
然后思考一个点可能代表多个子串，但是他们的出现次数都是相同的，所以单个点的贡献为上面的单个贡献再乘上一个有几个子串
子串的个数为parent树父亲节点的最大长度减去该节点的最大长度
这样子在从根开始dfs，如果经过某个点只有一个后缀经过，就说明lcp结束了，就不用再搜该点了。
上面就求出了lcp的和
至于前面那个式子，只需要打个表找个规律发现是(n-1)*n*(n+1)/2就可以了
虽然常数大点但是还是后缀自动机复杂度的
但其实不用这么复杂，只要翻过来就可以建出原串后缀树，lcp就是后缀树的两个节点的lca，跑个树形dp就可以了。
代码因为没用链式前向星存边所以不开o2会t，但还是贴一下吧
#include<bits/stdc++.h> #define N 1000010 using namespace std; int n; int gg=0; struct SAM { struct point { int son[26],fa,len,mx; }t[N]; int cnt=1,last=1; int f[N],sz[N]; bool vis[N]; vector<int> g[N],e[N]; long long lcp=0ll; void add(int c) { int p=last; int np=++cnt; t[np].len=t[p].len+1; sz[np]=1; while(p&&(!t[p].son[c])) { t[p].son[c]=np; p=t[p].fa; } if(!p) t[np].fa=1; else { int q=t[p].son[c],nq; if(t[p].len+1==t[q].len) { t[np].fa=q; } else { nq=++cnt; t[nq]=t[q]; t[nq].len=t[p].len+1; t[q].fa=t[np].fa=nq; while(p&&(t[p].son[c]==q)) { t[p].son[c]=nq; p=t[p].fa; } } } last=np; } void dfs(int now) { t[now].mx=t[now].len-t[t[now].fa].len; for(int i=0;i<26;i++) { if(t[now].son[i]) e[t[now].son[i]].push_back(now); } for(int i=0;i<g[now].size();i++) { dfs(g[now][i]); sz[now]+=sz[g[now][i]]; } } void dfs1(int now) { vis[now]=1; for(int i=0;i<e[now].size();i++) { f[e[now][i]]++; if(!vis[e[now][i]]) { dfs1(e[now][i]); } } } void dfs3(int now) { vis[now]=1; if(f[now]) lcp+=t[now].mx*(1ll*sz[now]*(sz[now]-1)/2); for(int i=0;i<26;i++) { if(f[t[now].son[i]]&&sz[t[now].son[i]]>1&&(!vis[t[now].son[i]])) { dfs3(t[now].son[i]); } } } void solve() { for(int i=1;i<=cnt;i++) g[t[i].fa].push_back(i); dfs(1); sz[1]=0; memset(vis,0,sizeof(vis)); dfs1(last); memset(vis,0,sizeof(vis)); dfs3(1); long long len=1ll*n*(n-1)*(n+1)/2; printf("%lld ",len-2*lcp); } }sam; char s[500050]; int main() { scanf("%s",s); n=strlen(s); for(int i=0;i<n;i++) { sam.add(s[i]-'a'); } sam.solve(); }