不错的题目
看似无法做，n<=5e4,8s，根号算法？
暴力一：
n^2，+SAM上找匹配点的right集合sz，失配了直接退出
暴力二：
O(m)
统计过lca=x的路径，
没法直接合并，就间接合并！
把所有形如(z,x)(x,y)的路径在原串所有出现位置打上标记
原串每个点维护结束路径(zi,x)和开始路径(x,yi)个数（实际上只有char=a[x]的位置才有值），然后乘起来就是贡献
打标记：
SAM匹配
麻烦事是：这个是往某个字符串前面加字符，但是要在字符串末尾位置打上标记
（和通常SAM末尾+字符，末尾位置打标记不同）
要用到后缀树、前缀树
(z,x)路径是前缀树
(x,y)路径是后缀树（反串前缀树）
把parent树建成前缀树，走一下。
建树：
（第一次建后缀树）
1.每个节点随便记录一个parent树子树里的后缀出现位置pos[x]
2.预处理parent树每个边第一个字符（最多26条边），
3.可能在边上，所以状态用(p,l)记录：下面是p点，在p点上方l处。
trans，根据l大小进行讨论
打标记：
trans打上tag
最后直接下放
结合
设阈值B
size<=B用暴力一，不递归了，O(B^2*n/B)
size>B用暴力二，分治树节点个数不超O(B)最多进行O(Bm)
B取sqrt(n)即可
容斥？
暴力二离线处理共线，显然会重复。分治到下一层的时候为上一层去重。
也是根据size选择去重方法
Code
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}
template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Miracle{
const int N=;
int B;
char s[N];
int n,m;
char a[N];
struct node{
int nxt,to;
}e[*N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
ll ans;
struct SAM{
int ch[*N][],cnt,len[*N],fa[*N];
int son[*N][],nd;
int tag[*N],exi[*N],ad[*N],pos[*N];
int sz[*N];
char s[*N];
SAM(){
cnt=nd=;
}
void ins(int c,int l){
int p=nd;len[nd=++cnt]=l;
exi[cnt]=l;sz[cnt]=;
pos[cnt]=l; for(;p&&ch[p][c]==;p=fa[p]) ch[p][c]=nd;
if(!p){
fa[nd]=;return;
}
int q=ch[p][c];
if(len[q]==len[p]+){
fa[nd]=q;return;
}
len[++cnt]=len[p]+;
fa[cnt]=fa[q];fa[q]=fa[nd]=cnt;
for(reg i=;i<;++i) ch[cnt][i]=ch[q][i];
for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=cnt;
}
struct edge{
int nxt,to;
}e[*N];
int hd[*N],tot;
void add(int x,int y){
e[++tot].nxt=hd[x];
e[tot].to=y;hd[x]=tot;
}
void dfs(int x){//pushup sz!!!
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
dfs(y);
sz[x]+=sz[y];
if(!pos[x]) pos[x]=pos[y];
}
}
void pre(){
// cout<<s+1<<endl;
for(reg i=;i<=m;++i) ins(s[i]-'a',i);
for(reg i=;i<=cnt;++i) add(fa[i],i);
dfs();
}
void build(){
for(reg i=;i<=cnt;++i){
son[fa[i]][s[pos[i]-len[fa[i]]]-'a']=i;
}
}
// int jump(int p,int c){//return to cur ;
// return ch[p][c];
// }
void trans(pair<int,int>&st,int c,int ok){//and add tag
if(st.fi==) return;
if(st.se==){//to son
st.fi=son[st.fi][c];
st.se=len[st.fi]-len[fa[st.fi]];
}else{
int to=pos[st.fi]-len[st.fi]+st.se-;
if(s[to]-'a'==c){
st.se--;
}else st.fi=;
}
if(st.fi!=&&ok){
++tag[st.fi];
}
return;
}
void pushdown(int x){
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
tag[y]+=tag[x];
pushdown(y);
}
}
void calc(){
pushdown();
// cout<<" cnt "<<cnt<<endl;
// prt(tag,1,cnt);
for(reg i=;i<=cnt;++i){
if(exi[i]) ad[exi[i]]+=tag[i];
}
// prt(ad,1,m);
}
void clear(){
memset(tag,,sizeof tag);
memset(ad,,sizeof ad);
}
}sam1,sam2;//sam1:pre tree ///// sam2:suf tree
bool vis[N];
int sz[N],nowsz;
int rt;
void dfs3(int x,int fa,int p,int w){//sz < B // w=1/-1
p=sam1.ch[p][a[x]-'a'];
if(p){
ans+=(ll)w*sam1.sz[p];
}
else return ;//warinnig!!
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa||vis[y]) continue;
dfs3(y,x,p,w);
}
}
int sta[N],top;
void dfs2(int x,int fa){//qu chong
sta[++top]=x;
int p=;
for(reg i=top;i>=;--i) p=sam1.ch[p][a[sta[i]]-'a'];
dfs3(sta[],sta[],p,-);
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(vis[y]||y==fa) continue;
dfs2(y,x);
}
sta[top--]=;
}
void dfs4(int x,int fa){
dfs3(x,,,);
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa||vis[y]) continue;
dfs4(y,x);
}
} void fin(int x,int fa){
sz[x]=;
int mxsz=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;if(vis[y]||y==fa) continue;
fin(y,x);
sz[x]+=sz[y];
mxsz=max(mxsz,sz[y]);
}
mxsz=max(mxsz,nowsz-sz[x]);
if(mxsz<=nowsz/){
rt=x;
}
}
void dfs1(int x,int fa,pair<int,int>p1,pair<int,int>p2){
sz[x]=;
sam1.trans(p1,a[x]-'a',);
sam2.trans(p2,a[x]-'a',);
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(vis[y]||y==fa) continue;
dfs1(y,x,p1,p2);
sz[x]+=sz[y];
}
} void divi(int x,int fa){
// cout<<" divi "<<x<<" fa "<<fa<<" ans "<<ans<<endl;
if(nowsz<=B){
if(fa){
top=;sta[++top]=fa;
dfs2(x,);
}
dfs4(x,);
}else{
if(fa){
sam1.clear();sam2.clear();
pair<int,int>p1=mk(,),p2=mk(,);
sam1.trans(p1,a[fa]-'a',);
sam2.trans(p2,a[fa]-'a',);
dfs1(x,,p1,p2);
//cout<<" a[fa] "<<a[fa]<<endl;
sam1.calc();
sam2.calc(); for(reg i=;i<=m;++i){
ans-=(ll)sam1.ad[i]*sam2.ad[m-i+];
//cout<<" ii "<<i<<" "<<sam1.ad[i]<<" and "<<sam2.ad[m-i+1]<<endl;
}
}
// cout<<" after ans "<<ans<<endl;
// if(fa){
// top=0;sta[++top]=fa;
// dfs2(x,0);
// } rt=;fin(x,);
sam1.clear();sam2.clear();
dfs1(rt,,mk(,),mk(,));//warning!! start from sam's rt
sam1.calc();
sam2.calc();
for(reg i=;i<=m;++i){
//if(s[i]==a[rt])
ans+=(ll)sam1.ad[i]*sam2.ad[m-i+];
} vis[rt]=;
int tmp=rt;
for(reg i=hd[rt];i;i=e[i].nxt){
int y=e[i].to;
if(!vis[y]) {
nowsz=sz[y];
divi(y,tmp);
}
}
}
}
int main(){
rd(n);rd(m);
B=sqrt(n);
int x,y;
for(reg i=;i<n;++i){
rd(x);rd(y);add(x,y);add(y,x);
}
scanf("%s",s+);
for(reg i=;i<=n;++i){
a[i]=s[i];
}
scanf("%s",sam1.s+);
memcpy(sam2.s,sam1.s,sizeof sam1.s);
reverse(sam2.s+,sam2.s+m+);
sam1.pre();sam1.build();
sam2.pre();sam2.build(); nowsz=n;
divi(,);
cout<<ans;
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/4/9 17:06:25
*/
总结
1.根号讨论暴力结合
2.点分治合并是难点，
要不然数据结构维护决策位置（树形Dp思路）
要不然都把上下路径都求出来放在一起，再人工拼凑（容斥思路）
3.有了前缀后缀树，妈妈再也不用担心一个串往前插入字符怎么匹配了！