bzoj 3238 [Ahoi2013]差异

Description

Input

一行，一个字符串S

Output

一行，一个整数，表示所求值

Sample Input

cacao

Sample Output

54

HINT

2<=N<=500000,S由小写英文字母组成

题解

反串的parent树是原串的后缀树

然后lcp就是他们的lca的深度，然后树形DP一下就好了

其实可以不用重建树直接拓扑排序，我这么写改了一上午也不对，拍了有2个小时。。于是直接重建了个树，神清气爽一遍A

#include <cstdio>
#include <cstring>
#define N 500010
using namespace std;
int dis[N<<1],fa[N<<1],ch[N<<1][26],sum[N<<1],siz[N<<1],sz=1,root=1,last=root,len;
char s[N];long long ans;
void insert(int x)
{
    int now=++sz,pre=last;last=now;
    dis[now]=dis[pre]+1,siz[now]=sum[now]=1;
    for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
    if (!pre) fa[now]=root;
    else if (dis[ch[pre][x]]==dis[pre]+1) fa[now]=ch[pre][x];
    else
    {
        int q=ch[pre][x],nows=++sz;dis[nows]=dis[pre]+1;
        memcpy(ch[nows],ch[q],sizeof ch[nows]);
        fa[nows]=fa[q],fa[q]=fa[now]=nows;
        for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
    }
}
struct edge
{
    int to,next;
}e[N<<1];
int st[N<<1],tot;
void add(int x,int y)
{
    e[++tot].next=st[x];
    e[tot].to=y,st[x]=tot;
}
void dfs(int now,int pre)
{
    for (int i=st[now];i;i=e[i].next)
        dfs(e[i].to,now),siz[now]+=siz[e[i].to];
    dis[now]-=dis[pre];
    ans+=1ll*siz[now]*(siz[now]-1)*dis[now];
}
main()
{
    scanf("%s",s+1),len=strlen(s+1);
    for (int i=len;i;i--) insert(s[i]-'a');
    for (int i=2;i<=sz;i++) add(fa[i],i);
    for (int i=st[root];i;i=e[i].next) dfs(e[i].to,root);
    printf("%lld\n",1ll*(len+1)*len/2*(len-1)-ans);
}