自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 21:57:48，当前版本为作者最后更新于2020-05-27 21:56:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一丶前言：

这道题真的好巧啊，是一道很好的训练后缀自动机与点分治 (与让自己自闭) 的题

二丶思路：

假设匹配串为$S$

显然，对匹配串$S$建后缀自动机

然后有一个十分简单的暴力思路，我们枚举树上的起始点$x$，然后从$x$开始直接dfs，在dfs的同时在SAM的DAG上跑匹配（如果找不到转移直接return）就好了。

假设到了后缀自动机的$y$号节点，$ans+=size[y]$就好了($size$是SAM点上的$right$集合大小)

对于学过后缀自动机 （如果你没学过来做这道题干嘛） 的各位来说，相信还是十分简单的，时间复杂度$O(n^2)$

接着，我们开始考虑正解。

看到我们要处理树上的所有路径，我们不由自主地会想到点分治。假设当前分治中心是$x$，我们该怎么处理？

直接算$\sum_{a} \sum_{b}[a$ 到 $x$组成的字符串在$S$出现的次数$]\times[x$到$b$组成的字符串在$S$出现的次数$]$ ？

这样显然不对，因为我们不能说前面出现在$S$，后面也出现在$S$，它们拼起来就一定出现在$S$

换句话说，它们在$S$中出现的位置不一定相同

再换句话说，我们要求的是：

$\sum_{p}\sum_{a}\sum_{b} [a$ 到 $x$组成的字符串出现在$S$且末尾为$p] \times [x$到$b$组成的字符串出现在$S$且起点是$p]$

(请看清楚上面那个和式qwq)

那我们只用枚举$p$，然后统计有多少个$a,b$满足$[a$到$x$组成的字符串出现在$S$且末尾为$p]$与$[x$到$b$组成的字符串出现在$S$且起点是$p]$就行了

显然两个统计是对称的（把$S$倒过来后者就变成了前者），所以我们只用考虑对第一种情况进行统计。

为了方便，下面假设$T$为是$a$到$x$形成的字符串，$pos[p]$为$S[1,p]$在SAM对应的节点

如果一个$T$是合法的，那么应该满足:

$\quad$1.$T$出现在$S$中

$\quad$2.$T$在SAM上对应的点的$right$集合包含$p$（既然它出现在$S$中那它肯定能对应SAM上一个点）

那我们只需要整一个$num$数组，并在$dfs$中途随时在找出$T$在SAM上的对应的节点$v$，并$num[v]++$就好了（如果没有直接return就好了）

问题就来了，如果我是在往$T$后面加字符，我直接在SAM的DAG上转移就好了，问题在于现在我是在往$T$前面加字符，我该怎么转移呢？

这个东西涉及到$Parent Tree$求儿子的问题，我们接下来再讲（当然你如果会了可以略过）

现在假设我们已经知道了在$T$前面加字符是如何转移的，并统计出了$num$数组，然后我们怎么求答案呢？

直接枚举$pos[p]$的所有祖先的$num$加起来？显然TLE

其实只要至上而下$num[x]+=num[fa[x]]$，然后$num[pos[p]]$就是答案了

现在我们回到上面的那个问题，我们往$T$前面加字符在SAM对应的点的变化情况。假设现在$T$对应SAM上的点$v$，并在$T$的前面加一个字符$c$，分两种情况讨论（假设$R[v]$表示$v$节点的任意一个$right$）：

1. $|T|<len[v]$，直接看接判断$[c==S[R[v]-|T|]]$，若为真$T$仍然对应$v$，否则$T$将不再出现在$S$中

2. $|T|==len[v]$，看有没有一个点$x$满足$fa[x]=v$，且$S[R[x]-len[v]]==c$，若有则$T$对应$x$，否则$T$将不再出现在$S$中

这样关于$ParentTree$的儿子的定义也呼之欲出了：

$son[x][p]$表示在$p+S[R[x]-len[x]+1,R[x]]$在$S$中对应的节点（这个数组可以在build时求出）

那么上面的第二条也可以改写成:

若$son[v][c]$存在，则$T$对应$son[v][c]$，否则$T$将不再出现在$S$中

时间复杂度为$O(nlogn+nm)$

等等，我们整了那么久，搞出来那么多东西，复杂度还变劣了？？（不做了下一道）

我们研究一下这个算法缺点在哪儿？其实缺点就在于，不管我们现在处理的分治子树多么的小，我们都需要把整个$m$遍历一遍，这样是很不划算的。

那咋办呢？等等，我们是不是还有一个$O(n^2)$的做法，那我们对小的分治子树直接进行$O(n^2)$的做法不就好了

自然考虑分块，对于小于等于$sqrt(n)$的分治子树直接暴力$n^2$，而对大的分治子树进行刚刚我们神奇的操作

还有个小问题 （几乎是所有点分治都记得要考虑的问题），$a$和$b$可能来自同一个子树，其实也很简单，直接容斥减掉就好了。

相信你现在几乎是一定一脸懵逼的 （如果不是那说明你太强了%%%），所以我们接下来结合代码理解一下吧。

三丶代码

//BadWaper gg
#include<bits/stdc++.h> 
#define inf 1e9
#define eps 1e-6
#define N 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
ll n,m;
struct edge
{
	ll next,to;
}e[N<<1];
ll head[N],cnt,vis[N];
ll pos1[N],pos2[N];
ll a[N],s[N];
char s1[N],s2[N];
ll size[N],C[N],p[N],ans;
ll minn=inf,rt,block;
struct SAM
{
	ll len[N],ch[N][26],fa[N];
	ll tot,son[N][26],R[N],size[N],num[N],last;
	ll p[N],c[N];
	ll s[N];
	SAM(){tot=last=1;}
	inline void insert(ll x)
	{
		ll nowp=++tot,p=last;len[nowp]=len[p]+1;size[nowp]=1;R[nowp]=len[nowp];
		while(p&&!ch[p][x])ch[p][x]=nowp,p=fa[p];
		if(!p)fa[nowp]=1;
		else 
		{
			ll q=ch[p][x];
			if(len[q]==len[p]+1)fa[nowp]=q;
			else
			{
				ll nowq=++tot;len[nowq]=len[p]+1;
				fa[nowq]=fa[q];fa[q]=nowq,fa[nowp]=nowq;
				for(register ll i=0;i<26;i++)ch[nowq][i]=ch[q][i];
				while(p&&ch[p][x]==q)ch[p][x]=nowq,p=fa[p];
			}
		}
		last=nowp;
	}//建SAM
	inline void build()
	{
		for(register ll i=1;i<=tot;i++)c[len[i]]++;
		for(register ll i=1;i<=m;i++)c[i]+=c[i-1];
		for(register ll i=1;i<=tot;i++)p[c[len[i]]--]=i;//基排
		for(register ll i=tot;i>=2;i--)
		{
			ll x=p[i];
			size[fa[x]]+=size[x];R[fa[x]]=R[x];//R是right集合内任意一个值，所以这里你爱咋搞咋搞啦qwq
			son[fa[x]][s[R[x]-len[fa[x]]]]=x;//求son
		}
	}
	inline void clear(){for(register ll i=1;i<=tot;i++)num[i]=0;}
	inline void calc(ll now,ll father,ll p,ll L)
	{
		if(len[p]==L)p=son[p][a[now]];//情况2
		else if(s[R[p]-L]!=a[now])p=0;//情况1
		if(!p)return ;//T不在S直接return
                num[p]++;
		for(register ll i=head[now];i;i=e[i].next)
		{
			if(e[i].to==father||vis[e[i].to])continue;
			calc(e[i].to,now,p,L+1);
		}
	}
	inline void pushdown()
	{
		for(register ll i=2;i<=tot;i++)//自上而下
		{
			ll x=p[i];
			num[x]+=num[fa[x]];
		}
	}
}S1,S2;
inline void add_edge(ll from,ll to){e[++cnt]=(edge){head[from],to};head[from]=cnt;}
void getroot(ll now,ll Ns,ll father)
{
	size[now]=1;ll maxn=-inf;
	for(register ll i=head[now];i;i=e[i].next)
	{
		if(e[i].to==father||vis[e[i].to])continue;
		getroot(e[i].to,Ns,now);size[now]+=size[e[i].to];
		maxn=max(maxn,size[e[i].to]);
	}
	maxn=max(maxn,Ns-size[now]);
	if(maxn<minn)minn=maxn,rt=now;
}//点分治求根
void dfs1(ll now,ll father)
{
	p[++p[0]]=now;
	for(register ll i=head[now];i;i=e[i].next)
	{
		if(e[i].to==father||vis[e[i].to])continue;
		dfs1(e[i].to,now);
	}
}//n^2暴力
void dfs2(ll now,ll father,ll x)
{
	x=S1.ch[x][a[now]];if(!x)return ;
	ans+=S1.size[x];
	for(register ll i=head[now];i;i=e[i].next)
	{
		if(e[i].to==father||vis[e[i].to])continue;
		dfs2(e[i].to,now,x);
	}
}//n^2暴力
void calc(ll x,ll father,ll f)
{
	S1.clear(),S2.clear();
	if(father)
	{
		S1.calc(x,0,S1.son[1][a[father]],1);
		S2.calc(x,0,S2.son[1][a[father]],1);
	}
	else {S1.calc(x,0,1,0);S2.calc(x,0,1,0);}
	S1.pushdown();S2.pushdown();
	for(register ll i=1;i<=m;i++)
	{
		ans+=f*S1.num[pos1[i]]*S2.num[pos2[m-i+1]];
	}//统计答案，注意因为串反过来了所以后面是m-i+1
}
void DFS(ll now,ll father)
{
	C[now]=1;
	for(register ll i=head[now];i;i=e[i].next)
	{
		if(e[i].to==father||vis[e[i].to])continue;
		DFS(e[i].to,now);C[now]+=C[e[i].to];
	}
}//求分治子树大小
void dfs(ll now,ll Ns)
{
	if(Ns<=block)
	{
		p[0]=0;dfs1(now,0);
		for(register ll i=1;i<=p[0];i++)dfs2(p[i],0,1);
		return ;
	}//n^2暴力
	vis[now]=1;calc(now,0,1);DFS(now,0);
	for(register ll i=head[now];i;i=e[i].next)
	{
		if(vis[e[i].to])continue;
		calc(e[i].to,now,-1);//容斥，把同一子树的答案容斥掉
                minn=inf,rt=0;
		getroot(e[i].to,C[e[i].to],0);dfs(rt,C[e[i].to]);
	}
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read();block=sqrt(n);
	for(register ll i=1;i<n;i++)
	{
		ll x=read(),y=read();
		add_edge(x,y);add_edge(y,x);
	}
	scanf("%s",s1+1);
	for(register ll i=1;i<=n;i++)a[i]=s1[i]-'a';
	scanf("%s",s2+1);
	for(register ll i=1;i<=m;i++)s[i]=s2[i]-'a';
	for(register ll i=1;i<=m;i++)S1.insert(s[i]),pos1[i]=S1.last,S1.s[i]=s[i];
	reverse(s+1,s+m+1);//把串翻转之后第二个统计与第一个统计类似
	for(register ll i=1;i<=m;i++)S2.insert(s[i]),pos2[i]=S2.last,S2.s[i]=s[i];
	S1.build();S2.build();
	getroot(1,n,0);dfs(rt,n);
	printf("%lld\n",ans);
	return 0;
}

四丶后记

我们做一道题不仅仅是要搞懂这道题怎么做，更要学会从这道题上反思与总结。

在平时的SAM学习中，我们几乎只用过在字符串后加字符（跑DAG），或者是在字符串前删字符（跳ParentTree），但这道题特殊之处就在于我们是在字符串前加入字符，并由此定义出了ParentTree上儿子的定义。（如果是在字符串后面删字符该怎么做呢qwq）

这是我从这道题收获到的东西，当然每个人收获到的东西多半都不一样，希望你也能从我的题解和这道题上有一定收获。

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq

这篇题解大部分我认为人人皆知的东西我就没定义了，往谅解qwq