这个是真——可持久化字典树.....
code:
#include <bits/stdc++.h>
#define N 100006
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,edges,Q,tot;
char val[N<<1][12];
int hd[N],to[N<<1],nex[N<<1],top[N],size[N],dep[N],fa[N],rt[N],son[N];
struct node
{
int ch[27],cnt;
}t[N*27];
void add(int u,int v,char str[])
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
for(int i=strlen(str),j=0;j<i;++j) val[edges][j]=str[j];
}
void insert(int pre,int u,char str[])
{
int last=rt[pre];
int len=strlen(str);
int now=rt[u]=++tot;
t[now]=t[last];
++t[now].cnt;
for(int i=0;i<len;++i)
{
t[now].ch[str[i]-'a']=++tot;
last=t[last].ch[str[i]-'a'];
now=tot;
t[now]=t[last];
++t[now].cnt;
}
}
int query(int x,char str[])
{
int len=strlen(str);
for(int i=0;i<len;++i) x=t[x].ch[str[i]-'a'];
return t[x].cnt;
}
void dfs1(int u,int ff)
{
fa[u]=ff,dep[u]=dep[ff]+1,size[u]=1;
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==ff) continue;
insert(u,v,val[i]), dfs1(v,u), size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(int i=hd[u];i;i=nex[i]) if(to[i]!=fa[u]&&to[i]!=son[u]) dfs2(to[i],to[i]);
}
int LCA(int x,int y)
{
while(top[x]!=top[y]) dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
int main()
{
// setIO("input");
int i,j;
scanf("%d",&n);
for(i=1;i<n;++i)
{
int x,y;
char str[12];
scanf("%d%d%s",&x,&y,str);
add(x,y,str),add(y,x,str);
}
dfs1(1,0);
dfs2(1,1);
scanf("%d",&Q);
while(Q--)
{
int x,y,lca;
char str[13];
scanf("%d%d%s",&x,&y,&str);
lca=LCA(x,y);
printf("%d\n",query(rt[x],str)+query(rt[y],str)-2*query(rt[lca],str));
}
return 0;
}