题面

SAM 里面塞了 2 个 dfs

我代码实现真的好垃圾啊，调了好久

const ll N=2e5+5;
int n,m,K;
ll ans,res;
char s[N],t[N];
struct SAM{
	int qwq,las=1,tot=1,f[N],seg[N];
	int len[N],fa[N],ch[N][27],ch2[N][27],siz[N],pos[N];
	char tc[N];
	vector<int>v[N];
	void add(int c,int id){
		int p=las,np=las=++tot;
		len[np]=len[p]+1;
		seg[id]=np,siz[np]=1,pos[np]=id;
		for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
		if(!p) fa[np]=1;
		else{
			int q=ch[p][c];
			if(len[q]==len[p]+1) fa[np]=q;
			else{
				int nq=++tot;
				for(int i=0;i<26;i++) ch[nq][i]=ch[q][i];
				fa[nq]=fa[q];
				fa[np]=fa[q]=nq;
				len[nq]=len[p]+1;
				for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
			}
		}
	}
	void dfs(int x){
		for(int i=0;i<v[x].size();i++){
			dfs(v[x][i]);
			siz[x]+=siz[v[x][i]];
			if(!pos[x]) pos[x]=pos[v[x][i]]; 
		}
		ch2[fa[x]][tc[pos[x]-len[fa[x]]]-'a']=x;
	}
	void dfs2(int x){
		for(int i=0;i<v[x].size();i++){
			f[v[x][i]]+=f[x];
			dfs2(v[x][i]);
		}
	}
	void pre(){
		for(int i=1;i<=qwq;i++) add(tc[i]-'a',i);
		for(int i=2;i<=tot;i++) v[fa[i]].push_back(i);
		dfs(1);
//		for(int i=1;i<=tot;i++) printf("%d ",fa[i]);
//		puts("");
//		for(int i=1;i<=tot;i++) printf("%d ",siz[i]);
//		puts("");
//		for(int i=1;i<=qwq;i++) printf("%d ",seg[i]);
//		puts("");
	}
	int get(int x,int y,char c){
		if(len[x]==y) x=ch2[x][c-'a'];
		else{
			if(tc[pos[x]-y]!=c) x=0;
		}
		return x;
	}
}Z,F;
int now,siz[N],maxx[N],rt,tot1;bool vis[N];vector<int>v[N];
void dfs1(int x,int fa){
	siz[x]=1,tot1++,maxx[x]=0;
	for(int i=0;i<v[x].size();i++)
		if(v[x][i]!=fa&&!vis[v[x][i]]){
			dfs1(v[x][i],x),siz[x]+=siz[v[x][i]];
			maxx[x]=max(maxx[x],siz[v[x][i]]);
		}
}
void dfs2(int x,int fa){
	for(int i=0;i<v[x].size();i++)
		if(v[x][i]!=fa&&!vis[v[x][i]])
			dfs2(v[x][i],x);
	maxx[x]=max(maxx[x],tot1-siz[x]);
	if(maxx[x]<maxx[rt]) rt=x;
}
int getrt(int x){tot1=0,rt=x;dfs1(x,0),dfs2(x,0);return rt;}
void dfs3(int to,int x,int fa,bool flag){
	flag|=(x==now);
	if(!to) return ;
	if(flag) res+=Z.siz[to];
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==fa) continue;
		if(vis[v[x][i]]) continue;
		dfs3(Z.ch[to][s[v[x][i]]-'a'],v[x][i],x,flag);
	}
}
void dfs4(int x,int fa){
	dfs3(Z.ch[1][s[x]-'a'],x,0,0);
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==fa) continue;
		if(vis[v[x][i]]) continue;
		dfs4(v[x][i],x);
	}
}
void dfs5(int to,int y,int x,int fa){
	if(!to) return ;
	Z.f[to]++;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==fa) continue;
		if(vis[v[x][i]]) continue;
		dfs5(Z.get(to,y,s[v[x][i]]),y+1,v[x][i],x);
	}
}
void dfs6(int to,int y,int x,int fa){
	if(!to) return ;
	F.f[to]++;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==fa) continue;
		if(vis[v[x][i]]) continue;
		dfs6(F.get(to,y,s[v[x][i]]),y+1,v[x][i],x);
	}
}
void dfs7(int to,int x,int fa){
//	printf("7 %d %d %d\n",x,to,Z.siz[to]);
	if(!to) return ;
	res+=Z.siz[to];
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==fa) continue;
		if(vis[v[x][i]]) continue;
		dfs7(Z.ch[to][s[v[x][i]]-'a'],v[x][i],x);
	}
}
void dfs8(int to,int x,int fa){
//	printf("8 %d %d\n",x,to);
	if(!to) return ;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==fa) continue;
		if(v[x][i]==now){
			dfs7(Z.ch[Z.ch[to][s[now]-'a']][s[x]-'a'],x,now);
		}
		if(vis[v[x][i]]) continue;
		dfs8(Z.ch[to][s[v[x][i]]-'a'],v[x][i],x);
	}
}
void dfs9(int x,int fa){
	dfs8(Z.ch[1][s[x]-'a'],x,0);
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==fa) continue;
		if(vis[v[x][i]]) continue;
		dfs9(v[x][i],x);
	}
}
ll solve1(int x){
	res=0; dfs4(x,0);
	return res;
}
ll solve2(int x){
	for(int i=0;i<=Z.tot;i++) Z.f[i]=0;
	for(int i=0;i<=F.tot;i++) F.f[i]=0;
	res=0;
	dfs5(Z.ch[1][s[x]-'a'],1,x,0);
	dfs6(F.ch[1][s[x]-'a'],1,x,0);
	Z.dfs2(1);
	F.dfs2(1);
//	for(int i=1;i<=m;i++) printf("%d ",Z.f[Z.seg[i]]);
//	puts("");
//	for(int i=1;i<=m;i++) printf("%d ",F.f[F.seg[i]]);
//	puts("");
	for(int i=1;i<=m;i++) res+=(ll)Z.f[Z.seg[i]]*F.f[F.seg[m-i+1]];
	return res;
}
ll solve3(int x){
	res=0; dfs9(x,0);
	return res;
}
ll solve4(int x,int fa){
	for(int i=1;i<=Z.tot;i++) Z.f[i]=0;
	for(int i=1;i<=F.tot;i++) F.f[i]=0;
	res=0;
	dfs5(Z.ch[Z.ch[1][s[x]-'a']][s[fa]-'a'],2,x,fa);
	dfs6(F.ch[F.ch[1][s[x]-'a']][s[fa]-'a'],2,x,fa);
	Z.dfs2(1);
	F.dfs2(1);
//	for(int i=1;i<=m;i++) printf("%d ",Z.f[i]);
//	puts("");
//	for(int i=1;i<=m;i++) printf("%d ",F.f[i]);
//	puts("");
	for(int i=1;i<=m;i++) res+=(ll)Z.f[Z.seg[i]]*F.f[F.seg[m-i+1]];
	return res;
}
void build(int x){
	dfs1(x,0);
//	printf("%d::\n",x);
	now=x;
	if(siz[x]<=K){
		ans+=solve1(x);
//		printf("%d\n",solve1(x));
	}
	else{
		ans+=solve2(x);
//		printf("%d\n",solve2(x));
		vis[x]=1;
		for(int i=0;i<v[x].size();i++)
			if(!vis[v[x][i]]){
				if(siz[v[x][i]]<=K){
//					printf("%d %d\n",v[x][i],solve3(v[x][i]));
					ans-=solve3(v[x][i]);
				}
				else{
//					printf("%d %d\n",v[x][i],solve4(v[x][i],x));
					ans-=solve4(v[x][i],x);
				}
			}
	} 
	vis[x]=1;
	for(int i=0,y;i<v[x].size();i++)
		if(!vis[v[x][i]]){
			y=getrt(v[x][i]);
			build(y);
		}
}