题解：首先所有后缀都在最后一个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=; struct SAM
{
struct point
{
int son[],fa,len,mx;
}t[N]; int cnt=,last=;
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+;
sz[np]=;
while(p&&(!t[p].son[c]))
{
t[p].son[c]=np;
p=t[p].fa;
}
if(!p) t[np].fa=;
else
{
int q=t[p].son[c],nq;
if(t[p].len+==t[q].len)
{
t[np].fa=q;
}
else
{
nq=++cnt;
t[nq]=t[q];
t[nq].len=t[p].len+;
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=;i<;i++)
{
if(t[now].son[i]) e[t[now].son[i]].push_back(now);
}
for(int i=;i<g[now].size();i++)
{
dfs(g[now][i]);
sz[now]+=sz[g[now][i]];
}
} void dfs1(int now)
{
vis[now]=;
for(int i=;i<e[now].size();i++)
{
f[e[now][i]]++;
if(!vis[e[now][i]])
{
dfs1(e[now][i]);
}
}
} void dfs3(int now)
{
vis[now]=;
if(f[now]) lcp+=t[now].mx*(1ll*sz[now]*(sz[now]-)/);
for(int i=;i<;i++)
{
if(f[t[now].son[i]]&&sz[t[now].son[i]]>&&(!vis[t[now].son[i]]))
{
dfs3(t[now].son[i]);
}
}
} void solve()
{
for(int i=;i<=cnt;i++) g[t[i].fa].push_back(i);
dfs();
sz[]=;
memset(vis,,sizeof(vis));
dfs1(last);
memset(vis,,sizeof(vis));
dfs3();
long long len=1ll*n*(n-)*(n+)/;
printf("%lld\n",len-*lcp);
} }sam; char s[]; int main()
{
scanf("%s",s);
n=strlen(s);
for(int i=;i<n;i++)
{
sam.add(s[i]-'a');
}
sam.solve();
}