后缀自动机的parent树就是反串的后缀树。
所以只需要反向构建出后缀树，就可以乱搞了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define maxn 1000005 struct sam{
ll ans;
char s[maxn];
int cnt,last,siz[maxn],len;
int go[maxn][26],fa[maxn],l[maxn];
int h[maxn],to[maxn],ne[maxn],en;
void addedge(int a,int b)
{to[en]=b;ne[en]=h[a];h[a]=en++;}
void init()
{
cnt=last=1;
memset(go,0,sizeof go);
}
void add(int x)
{
// printf("add %d\n",x);
int p=last,np=last=++cnt;l[np]=l[p]+1;//printf("np is %d\n",np);
for (;p&&!go[p][x];p=fa[p]) go[p][x]=np;
if (!p) fa[np]=1;
else
{
int q=go[p][x];
if (l[q]==l[p]+1) fa[np]=q;
else
{
int nq=++cnt; l[nq]=l[p]+1; //printf("nq is %d\n",nq);
memcpy(go[nq],go[q],sizeof go[q]);
fa[nq]=fa[q];
fa[np]=fa[q]=nq;
for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;
}
}
siz[np]=1;
// printf("siz %d is %d\n",np,1);
}
void read()
{
scanf("%s",s+1); len=strlen(s+1);
D(i,len,1) add(s[i]-'a');
}
void dfs(int o)
{
// printf("dfs on %d len is %d\n",o,l[o]);
for (int i=h[o];i>=0;i=ne[i])
{ dfs(to[i]);
// printf("%d & %d -= %lld\n",o,to[i],(ll)2*siz[o]*siz[to[i]]*l[o]);
ans-=(ll)2*siz[o]*siz[to[i]]*l[o];
siz[o]+=siz[to[i]];
}
}
void work()
{
ans=(ll)(len-1)*(len+1)*len/2;
dfs(1);
printf("%lld\n",ans);
}
void build()
{
en=0;
memset(h,-1,sizeof h);
F(i,1,cnt) addedge(fa[i],i);
}
}SAM; int main()
{
SAM.init();
SAM.read();
SAM.build();
SAM.work();
}