题解 P4218 【[CTSC2010]珠宝商】
WAPER4EVER
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$可能来自同一个子树，其实也很简单，直接容斥减掉就好了。
相信你现在几乎是一定一脸懵逼的 ~~（如果不是那说明你太强了%%%）~~，所以我们接下来结合代码理解一下吧。
### 三丶代码
```cpp
//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~~