RT，WA了只有55分，没找到和我一样的。记录

仿照第一篇题解写的。求调。

#include<bits/stdc++.h>

//#define RELEASE
#ifndef RELEASE
	//#define FL
	#define DB puts("debug")
#endif 

using namespace std;

typedef long long ll;
const int S=1000003,NN=S*2;

inline int read(){
	char c=getchar();
	int res=0;
	bool b=0;
	while(c>'9'||c<'0')b=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
	return b?-res:res;
}

int n;
ll ans;
char s[S+10];
int ch[NN+10][26],ln[NN+10],lnk[NN+10],siz[NN+10],tn=1,lst=1;
int tmp[NN+10];

void Ins(int c){
	int p=lst,u=lst=++tn;
	ln[u]=ln[p]+1;
	siz[u]=1;
	while(p&&!ch[p][c])
		ch[p][c]=u,p=lnk[p];
	if(!p)
		return lnk[u]=1,void();
	int q=ch[p][c];
	if(ln[q]==ln[p]+1)
		return lnk[u]=q,void();
	int cln=++tn;
	lnk[cln]=lnk[q],lnk[q]=lnk[u]=cln;
	ln[cln]=ln[p]+1;
	for(register int i=0;i<26;i++)
		ch[cln][i]=ch[q][i];
	while(p&&ch[p][c]==q)
		ch[p][c]=cln;
}

bool Cmp(int a,int b){
	return ln[a]>ln[b];
}

void Calc(){
	for(register int i=1;i<=tn;++i)
		tmp[i]=i;
	sort(tmp+1,tmp+1+tn,Cmp);
	for(register int i=1;i<=tn;++i){
		int t=tmp[i];
		siz[lnk[t]]+=siz[t];
		ans+=(ll)(ln[t]-ln[lnk[t]])*siz[t]*(n-siz[t]);
	}
}

int main(){
	#ifdef fl
		freopen(".in","r",stdin);
		#ifndef db
			freopen(".out","w",stdout);
		#endif
	#endif
	scanf("%s",s+1);
	n=strlen(s+1);
	for(register int i=1;i<=n;++i)
		Ins(s[i]-'a');
	Calc();
	printf("%lld\n",ans);
	#ifdef db
		system("pause");
	#endif
	return 0;
}
/*
 * \________     \______  \__      \__      \__  \___      \__  \__       \__  \__
 * \__     \__     \__    \__     \____     \__  \____     \__  \__       \__  \__
 * \__      \__    \__     \__   \__ \__   \__   \__\__    \__  \__       \__  \__
 * \__      \__    \__     \__   \__ \__   \__   \__ \__   \__  \__       \__  \__
 * \__      \__    \__     \__   \__ \__   \__   \__  \__  \__  \__       \__  \__
 * \__      \__    \__      \__ \__   \__ \__    \__   \__ \__  \__       \__  \__
 * \__      \__    \__      \__ \__   \__ \__    \__    \__\__  \__       \__  \__
 * \__     \__     \__       \____     \____     \__     \____   \__     \__   \__
 * \________     \______      \__       \__      \__      \___     \______     \__________
 *
 * \___________      \_____     \__
 *      \__        \___  \___   \__
 *      \__       \___     \__  \__
 *      \__      \__            \__
 *      \__      \__            \__
 *      \__      \__            \__
 *      \__       \___     \__  \__
 *      \__        \___  \___   \__
 *      \__          \_____     \__________
*/