【题意】给定长度为n的小写字母字符串，令Ti表示以i开头的后缀，求Σ[Ti+Tj-2*lcp(Ti,Tj)]，1<=i<j<=n。

【算法】后缀自动机

【题解】Σ(Ti+Tj)只与n有关，那么关键在于计算Σ2*lcp(Ti,Tj)。

对逆序串建后缀自动机，其parent树就是原串的后缀树，lcp(Ti,Tj)就是两个后缀在后缀树上的LCA。

那么每个节点的贡献是：2*C(Right(x),2)*Len(x)，Right集合的计算先把所有的后缀节点（即每次的np）赋值为1，然后dfs即可。

也可以不用组合数，考虑实际意义——每个节点的贡献是：(Right(x)^2-ΣRight(y)^2)*Len(x),y=son(x)，如果x自己是后缀节点括号里再-1，这是从每个Right要在此节点和其它Right结合的思想。

SAM记得双倍空间。

#include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int maxn=1000010;//struct tree{
    int len,fa,t[30];}t[maxn];struct edge{
    int v,from;}e[maxn*2];int last,n,tot=0,root,cnt,first[maxn];ll f[maxn],ans=0;bool mark[maxn];char s[maxn];void insert(int c){    int np=++tot;    t[np].len=t[last].len+1;    f[np]=1;    int x=last;    while(x&&!t[x].t[c])t[x].t[c]=np,x=t[x].fa;    last=np;    if(!x)t[np].fa=root;else{        int y=t[x].t[c];        if(t[y].len==t[x].len+1)t[np].fa=y;else{            int nq=++tot;            t[nq]=t[y];            t[nq].len=t[x].len+1;            t[nq].fa=t[y].fa;t[y].fa=t[np].fa=nq;            while(x&&t[x].t[c]==y)t[x].t[c]=nq,x=t[x].fa;        }    }}void ins(int u,int v){cnt++;e[cnt].v=v;e[cnt].from=first[u];first[u]=cnt;}void dfs(int x){    ll sum=f[x]*f[x];    for(int i=first[x];i;i=e[i].from){        dfs(e[i].v);        f[x]+=f[e[i].v];        sum+=f[e[i].v]*f[e[i].v];    }    ans+=(f[x]*f[x]-sum)*t[x].len;}int main(){    scanf("%s",s+1);n=strlen(s+1);    root=tot=last=1;    for(int i=n;i>=1;i--)insert(s[i]-'a');    for(int i=2;i<=tot;i++)ins(t[i].fa,i);    dfs(root);    ll sum=0;    for(int i=1;i