bzoj 3926 [Zjoi2015]诸神眷顾的幻想乡

7 3

0 2 1 2 1 0 0

1 2

3 4

3 5

4 6

5 7

2 5

30

题解

#include <cstdio>
#include <cstring>
#define N 100010
using namespace std;
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int dis[N*40],fa[N*40],ch[N*40][11],sz=1,root=1,last=root;
void insert(int x)
{
int now=ch[last][x],pre=last;
if (now)
if (dis[now]==dis[pre]+1) last=now;
else
{
int nows=++sz;dis[nows]=dis[pre]+1;
memcpy(ch[nows],ch[now],sizeof ch[now]);
fa[nows]=fa[now],fa[now]=nows;
for (;pre && ch[pre][x]==now;pre=fa[pre]) ch[pre][x]=nows;
last=nows;
}
else
{
now=++sz,dis[now]=dis[pre]+1;last=now;
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;
}
}
}
void getans()
{
long long ans=0;
for (int i=1;i<=sz;i++)
ans+=dis[i]-dis[fa[i]];
printf("%lld\n",ans);
}
struct edge
{
int to,next;
}e[N*2];
int st[N],tot,v[N],d[N];
{
e[++tot].next=st[x];
e[tot].to=y,st[x]=tot;
}
void dfs(int now,int pre)
{
insert(v[now]);
int te=last;
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=pre)
dfs(e[i].to,now),last=te;
}
int n,m,x,y;
main()
{