-
题解：
- 树上的串匹配，模式串的总长$|S|$，令$\overline {S} $为$S$的反串；
- 对$S$和$\overline {S} $分别建自动机
- $u -> v$可以分成三个部分去统计
- ①跨越了$lca(u, v)$的部分，长度不会超过$2|S|$，$kmp$暴力统计答案；
- ②$(u,lca)$上不跨越$lca$的部分，差分变成两个到根的询问；
- ②$(lca,v)$上不跨越$lca$的部分，差分变成两个到根的询问；
- $dfs$原树并记录走到两个自动机的节点$x / y$，$BIT$维护$fail$树的子树和:
- 进入时$add(x / y,1)$，回溯时$add(x / y,-1)$；
- ②在$\overline {S} $里查，①在$S$里查即可处理所有询问；
- (突然发现似乎不用建两个自动机，直接建在一起就好了TAT所以别学大米饼丑陋的代码)
- 一个弱化版：bzoj3881,另外树剖$lca$常数小，好些，点分治常用$rmq$求$lca$;
#include<bits/stdc++.h>
#define rg register
#define il inline
using namespace std;
const int N=,M=;
int n,m,o=,hd[N],Hd[N],O=,tp[N],sz[N],sn[N],dfn[N],idx;
int q[N],head,tail,fa[N],f[N],pos[N],dep[N],ans[N];
struct Edge{int v,nt,c;}E[N<<];
struct Qury{int p,x,y,nt;}Q[N<<];
char s[N],t[N],fm[N];
il void adde(int u,int v,int c){
E[o]=(Edge){v,hd[u],c};hd[u]=o++;
E[o]=(Edge){u,hd[v],c};hd[v]=o++;
}
il void addq(int u,int p,int x,int y){
Q[O]=(Qury){p,x,y,Hd[u]};Hd[u]=O++;
}
void dfs1(int u,int F){
sz[u]=;sn[u]=;
dep[u]=dep[fa[u]=F]+;
for(rg int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==F)continue;
fm[v]=E[i].c+'a';
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[sn[u]])sn[u]=v;
}
}
void dfs2(int u,int T){
dfn[pos[u]=++idx]=u;tp[u]=T;
if(sn[u])dfs2(sn[u],T);
for(rg int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==fa[u]||v==sn[u])continue;
dfs2(v,v);
}
}
il int go(int u,int d){
int tu=tp[u];
while(dep[u]-dep[tu]<d){
d-=dep[u]-dep[tu]+;
u=fa[tu],tu=tp[u];
}
return dfn[pos[tu]+dep[u]-dep[tu]-d];
}
il int lca(int u,int v){
int tu=tp[u],tv=tp[v];
while(tu!=tv)if(dep[tu]>dep[tv])u=fa[tu],tu=tp[u];
else v=fa[tv],tv=tp[v];
return dep[u]<dep[v]?u:v;
}
il int kmp(int x,int y,int z,int ls){
int lt=,tl=,re=;
while(dep[x]>dep[z])t[++lt]=fm[x],x=fa[x];
tl=lt=lt+dep[y]-dep[z];
while(dep[y]>dep[z])t[tl--]=fm[y],y=fa[y];
if(lt<ls)return ;
f[]=f[]=;
for(rg int i=,j=;i<ls;f[++i]=j){
while(j&&s[i+]!=s[j+])j=f[j];
if(s[i+]==s[j+])j++;
}
for(rg int i=,j=;i<=lt;i++){
while(j&&t[i]!=s[j+])j=f[j];
if(t[i]==s[j+])j++;
if(j==ls)re++,j=f[j];
}
return re;
}
struct AC{
int cnt,fl[M],fa[M],st[M],ed[M],idx,c[M],ch[M][],pos[N],hd[N],o;
struct Edge{int v,nt;}E[N];
il void adde(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++;}
il void add(int x,int y){for(;x<=idx;x+=x&-x)c[x]+=y;}
il int ask(int x){int re=;for(;x;x-=x&-x)re+=c[x];return re;}
il void ins(int cur,int l){
int x=;
for(int i=,y;i<=l;i++){
if(!ch[x][y=s[i]-'a'])ch[x][y]=++cnt;
x=ch[x][y];
}pos[cur]=x;
}
il void dfs(int u){
st[u]=++idx;
for(rg int i=hd[u];i;i=E[i].nt)dfs(E[i].v);
ed[u]=idx;
}
il void bfs(){
o=;head=tail=;
for(int i=;i<;i++)if(ch[][i]){
q[++tail]=ch[][i];
adde(,ch[][i]);
}
while(head<tail){
int u=q[++head];
for(rg int i=;i<;i++){
int&v=ch[u][i];
if(!v){v=ch[fl[u]][i];continue;}
fl[v]=ch[fl[u]][i];
q[++tail]=v;
adde(fl[v],v);
}
}
dfs();
}
il int que(int x){return ask(ed[pos[x]]) - ask(st[pos[x]]-);}
}ac[];
void dfs3(int u,int y0,int y1){
ac[].add(ac[].st[y0],);
ac[].add(ac[].st[y1],);
for(int i=Hd[u];i;i=Q[i].nt){
ans[Q[i].x]+=ac[Q[i].p].que(Q[i].x)*Q[i].y;
}
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v , c=E[i].c;
if(E[i].v==fa[u])continue;
dfs3(v,ac[].ch[y0][c],ac[].ch[y1][c]);
}
ac[].add(ac[].st[y0],-);
ac[].add(ac[].st[y1],-);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("bzoj4231.in","r",stdin);
freopen("bzoj4231.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(rg int i=;i<n;i++){
int u,v;
scanf("%d%d%s",&u,&v,s+);
adde(u,v,s[]-'a');
}
dfs1(,);dfs2(,);
for(rg int i=;i<=m;i++){
int u,v,w,l,t1,t2;
scanf("%d%d%s",&u,&v,s+);
w=lca(u,v);
l=strlen(s+);
t1=go(u,max(,dep[u]-dep[w]-l+));
t2=go(v,max(,dep[v]-dep[w]-l+));
ans[i]+=kmp(t1,t2,w,l);
ac[].ins(i,l);
for(rg int j=;j<=l>>;j++)swap(s[j],s[l-j+]);
ac[].ins(i,l);
if(t1!=u)addq(u,,i,),addq(t1,,i,-);
if(t2!=v)addq(v,,i,),addq(t2,,i,-);
}
ac[].bfs();
ac[].bfs();
dfs3(,,);
for(rg int i=;i<=m;i++){printf("%d\n",ans[i]);}
return ;
}bzoj4231
$lca(q[i-1],q[i])$