大概是四节课写代码，三节课debug，七个长相差不多的dfs穿插其中…… 好了不吐槽了； 题意： 给定一棵点上有字母的树，和一个母串 求树上点两两之间 N2 条路径在母串中匹配次数和
这里采用的基本是《CTSC2010珠宝商新解》–许昊然的做法 首先考虑两种不同的暴力： 1.枚举端点dfs，SAM上跑转移 O(N2) 2.这个暴力比较特殊； 考虑一个作为路径lca的点A，则我们可以尝试用A子树中两条“半路径”拼出原路径； 不妨设A上字母为 i ,则需 (x,i) , (i,y) 构成（x,y）; 这个问题可以通过在正反串的后缀树上打标记，再下放至叶子就可以合并了； 单次O(N)，总的 O(N2)
那么正解肯定是把他们拼起来啦； 解法1喜欢n较小的情况（当然soas解法2）； 解法2单次复杂度与子树大小无关的； 借助点分治这个平台，二者便可巧妙结合：
在点分治中，如果子树大小小于 N−−√ 便采用解法1，并停止递归； 如果子树大小大于 N−−√ 便采用解法2；
其中由于第一步子树之间相互独立，则最差 NN−−√ 第二步可以证明大小大于 N−−√ 的分治子树不超过 N−−√ 个，故也是 NN−−√
但参拜lct1999的题解得知论文有一个细节处理不当 即在分治去重中也是应该依据子树大小判断解法的
嗯…后缀树怎么求？ 一般的字符集小的前提下：SAM–>后缀树–>SA
附上写过最丑的代码…..
#include<bits/stdc++.h> #define rep(i,k,n) for(int i=k;i<=n;i++) #define rep2(i,k,n) for(int i=k;i>=n;i--) #define pa pair<int,int> #define mk make_pair #define fr first #define sc second using namespace std; typedef long long ll; const int N=1e5+7; const int inf=0x3f3f3f3f; struct tu{ struct E{ int to,next;E(int to=0,int next=0):to(to),next(next){} }edge[N<<1]; int head[N],tot; void init(){tot=0;} void add(int x,int y){ edge[++tot]=E(y,head[x]);head[x]=tot; } }T; int n,m; struct machine{ tu tree; int tot,fa[N],ch[N][26],len[N],val[N],nod[N],p,last,sz[N],a[N],c[N],rk[N],q[N],mx[N]; char s[N]; void init(){last=p=tot=0;} void extend(int c,int pos){ int x; p=last,last=x=++tot; len[x]=len[p]+1; nod[x]=sz[x]=1; mx[x]=pos; for(;!ch[p][c];p=fa[p])ch[p][c]=x; if(ch[p][c]!=x){ int q=ch[p][c]; if(len[p]+1==len[q]){ fa[x]=q; }else{ int nq=++tot; len[nq]=len[p]+1; fa[nq]=fa[q]; memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[q]=fa[x]=nq; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq; } } } void build(){ rep(i,1,m)extend(s[i]-'a',i); } void build_tree(){ tree.init(); rep(i,1,tot)tree.add(fa[i],i); memset(c,0,sizeof(c)); rep(i,1,tot)c[len[i]]++; rep(i,1,tot)c[i]+=c[i-1]; rep(i,1,tot)rk[i]=c[len[i]]--; rep(i,1,tot)q[rk[i]]=i; rep2(i,tot,1) sz[fa[q[i]]]+=sz[q[i]],mx[fa[q[i]]]=max(mx[fa[q[i]]],mx[q[i]]); } pa trans(pa x,char c){ int pos=x.fr; int now=x.sc; int l=mx[pos]-len[pos]+1; int r=mx[pos]-len[fa[pos]]; int who=r-now; if(who>=l && pos){ if(s[who]==c)return mk(pos,now+1); else return mk(-1,-1); }else{ for(int i=tree.head[pos];i;i=tree.edge[i].next){ int v=tree.edge[i].to; r=mx[v]-len[fa[v]]; if(s[r]==c)return mk(v,1); } return mk(-1,-1); } } void mem(){memset(val,0,sizeof(val));} void push_down(){ rep(i,1,tot) for(int j=tree.head[q[i]];j;j=tree.edge[j].next){ int v=tree.edge[j].to; val[v]+=val[q[i]]; } memset(a,0,sizeof(a)); rep(i,1,tot)if(nod[i])a[len[i]]=val[i]; } }t1,t2; int sz[N],mx[N],vis[N],root,S,Q,fa[N]; ll Ans=0,tmp; char V[N]; void getrt(int x,int f){ sz[x]=1,mx[x]=0; for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(!vis[v] && v!=f){ getrt(v,x); mx[x]=max(mx[x],sz[v]); sz[x]+=sz[v]; } }mx[x]=max(mx[x],S-sz[x]); if(mx[x]<mx[root])root=x; } void dfs3_1(int x,int f,pa now){ now=t1.trans(now,V[x]); if(now.fr==-1)return; t1.val[now.fr]++; for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(v!=f && !vis[v])dfs3_1(v,x,now); } } void dfs3_2(int x,int f,pa now){ now=t2.trans(now,V[x]); if(now.fr==-1)return; t2.val[now.fr]++; for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(v!=f && !vis[v])dfs3_2(v,x,now); } } ll sol1(int x,int f,pa now1,pa now2){ t1.mem();t2.mem(); if(now1.fr==-1 || now2.fr==-1)return 0; dfs3_1(x,f,now1); dfs3_2(x,f,now2); t1.push_down();t2.push_down(); ll ans=0; rep(i,1,m)ans+=1ll*t1.a[i]*t2.a[m-i+1]; return ans; } void dfs5(int x,int f,int an,int now,int ok){ now=t1.ch[now][V[x]-'a']; if(!now)return; if(x==an){ now=t1.ch[now][V[fa[x]]-'a']; if(!now)return; now=t1.ch[now][V[x]-'a']; if(!now)return; ok=1; f=0; } if(!ok)dfs5(fa[x],x,an,now,ok); else{ tmp+=t1.sz[now]; for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(v!=f && !vis[v] && v!=fa[x])dfs5(v,x,an,now,ok); } } } void dfs4(int x,int f,int an){ dfs5(x,0,an,0,0); for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(v!=f && !vis[v])dfs4(v,x,an); } } ll sol2(int x,int f){ tmp=0; dfs4(x,f,x); return tmp; } void way1(int x){ Ans+=sol1(x,0,mk(0,0),mk(0,0)); for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(!vis[v]){ if(sz[v]>Q){ Ans-=sol1(v,x,t1.trans(mk(0,0),V[x]),t2.trans(mk(0,0),V[x])); }else{ Ans-=sol2(v,x); } } } } void dfs2(int x,int f,int now){ now=t1.ch[now][V[x]-'a']; if(!now)return; tmp+=t1.sz[now]; for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(v!=f && !vis[v])dfs2(v,x,now); } } void dfs(int x,int f){ dfs2(x,0,0); for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(v!=f && !vis[v])dfs(v,x); } } void way2(int x){ tmp=0; dfs(x,0); } void Dfs(int x,int f){ fa[x]=f; sz[x]=1; for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(v!=f && !vis[v]){ Dfs(v,x); sz[x]+=sz[v]; } } } void go(int x){ if(sz[x]<=Q){way2(x);Ans+=tmp;} else { vis[x]=1; Dfs(x,0); way1(x); for(int i=T.head[x];i;i=T.edge[i].next){ int v=T.edge[i].to; if(!vis[v]){ S=sz[v],root=0,getrt(v,x); go(root); } } } } void solve(){ mx[0]=inf; S=n,root=0,getrt(1,0); go(root); } int main(){ scanf("%d%d",&n,&m); Q=sqrt(n)+1; int x,y;T.init(); rep(i,1,n-1){ scanf("%d%d",&x,&y); T.add(x,y); T.add(y,x); }scanf("%s%s",V+1,t1.s+1); t1.init();t2.init(); memcpy(t2.s,t1.s,sizeof(t1.s)); rep(i,1,m>>1)swap(t2.s[i],t2.s[m-i+1]); t1.build(); t2.build(); t1.build_tree(); t2.build_tree(); solve(); printf("%lld\n",Ans); }