这是一道裸的可持久化trie树。这个方法就不多说了，详见“初探主席树”及“cout on a tree”。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
int n,u,v,cnt,l,q;
int edgenum,vet[2*N],next[2*N],head[2*N],root[N];
int f[N],d[N],num[N],son[N],top[N];
struct node{int sum,son[30];}tr[10*N];
char str[15],s[N][15];
void add(int u,int v)
{
edgenum++;
vet[edgenum]=v;
next[edgenum]=head[u];
head[u]=edgenum;
}
void dfs(int u,int fa,int dep)
{
f[u]=fa;
d[u]=dep;
num[u]=1;
int maxnum=0;
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=fa)
{
dfs(v,u,dep+1);
num[u]+=num[v];
if (num[v]>maxnum){maxnum=num[v];son[u]=v;}
}
}
}
void dfs(int u,int number)
{
top[u]=number;
if (!son[u]) return;
dfs(son[u],number);
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=f[u]&&v!=son[u]) dfs(v,v);
}
}
int getlca(int u,int v)
{
while (top[u]!=top[v])
{
if (d[top[u]]<d[top[v]]) swap(u,v);
u=f[top[u]];
}
if (d[u]<d[v]) return u;else return v;
}
void change(int &p,int k,int dep)
{
tr[++cnt]=tr[p];p=cnt;tr[p].sum++;
if (dep==strlen(s[k])) return;
change(tr[p].son[s[k][dep]-'a'],k,dep+1);
}
int ask(int p,int dep)
{
if (p==0&&dep) return 0;
if (dep==l) return tr[p].sum;
return ask(tr[p].son[str[dep]-'a'],dep+1);
}
void dfs1(int u,int e)
{
if (u!=1){root[u]=root[f[u]];change(root[u],(e+1)>>1,0);}
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=f[u]) dfs1(v,e);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<n;i++)
{
scanf("%d%d%s",&u,&v,s[i]);
add(u,v);add(v,u);
}
dfs(1,0,1);
dfs(1,1);
dfs1(1,0);
scanf("%d",&q);
while (q--)
{
scanf("%d%d%s",&u,&v,str);
l=strlen(str);
printf("%d\n",ask(root[u],0)+ask(root[v],0)-2*ask(root[getlca(u,v)],0));
}
}
还有一种我在练习赛上自己yy的一种方法。然而，有些复杂（我是有自知之明的），文字解释起来非常复杂，代码放着，有兴趣的人可以自己研究一下。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
typedef long long ll;
int n,q,cnt,l;
int edgenum,Edgenum,vet[2*N],next[2*N],head[2*N],Vet[10*N],Next[10*N],Head[10*N],x[N],y[N],a[N],b[N],lca[N];
ll dis[2*N],Ask[10*N],P[10*N],p[10*N],ans[N],mi[20],w[N],c[N],d[N];
int f[N],de[N],num[N],son[N],top[N],tr[10*N];
char s[20];
void add(int u,int v,ll w)
{
edgenum++;
vet[edgenum]=v;
next[edgenum]=head[u];
head[u]=edgenum;
dis[edgenum]=w;
}
void dfs(int u,int fa,int dep)
{
f[u]=fa;
de[u]=dep;
num[u]=1;
int maxnum=0;
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=fa)
{
dfs(v,u,dep+1);
num[u]+=num[v];
if (num[v]>maxnum){maxnum=num[v];son[u]=v;}
}
}
}
void dfs(int u,int number)
{
top[u]=number;
if (!son[u]) return;
dfs(son[u],number);
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=f[u]&&v!=son[u]) dfs(v,v);
}
}
int getlca(int u,int v)
{
while (top[u]!=top[v])
{
if (de[top[u]]<de[top[v]]) swap(u,v);
u=f[top[u]];
}
if (de[u]<de[v]) return u;else return v;
}
void Add(int u,int v,ll w,ll opt)
{
Edgenum++;
Vet[Edgenum]=v;
Next[Edgenum]=Head[u];
Head[u]=Edgenum;
Ask[Edgenum]=w;
P[Edgenum]=opt;
}
int asksum(ll x)
{
int ans=0;
while (x)
{
ans+=tr[x];
x-=((x)&(-x));
}
return ans;
}
void tradd(ll x,int val)
{
while (x<=cnt)
{
tr[x]+=val;
x+=((x)&(-x));
}
}
void dfs(int u)
{
for (int e=Head[u];e;e=Next[e])
{
int v=Vet[e];
ans[v]+=(ll)asksum(Ask[e])*P[e];
}
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=f[u])
{
tradd(dis[e],1);
dfs(v);
tradd(dis[e],-1);
}
}
}
int main()
{
freopen("strings.in","r",stdin);
freopen("strings.out","w",stdout);
scanf("%d",&n);
mi[0]=1;
for (int i=1;i<=10;i++) mi[i]=mi[i-1]*31;
for (int i=1;i<n;i++)
{
scanf("%d%d%s",&x[i],&y[i],s);
l=strlen(s);
w[i]=0;
for (int j=0;j<l;j++)
w[i]=w[i]*31+s[j]-'a'+1;
w[i]=w[i]*mi[10-l];
p[++cnt]=(ll)w[i];
add(x[i],y[i],w[i]);add(y[i],x[i],w[i]);
}
dfs(1,0,1);
dfs(1,1);
scanf("%d",&q);
for (int i=1;i<=q;i++)
{
scanf("%d%d%s",&a[i],&b[i],s);
lca[i]=getlca(a[i],b[i]);
c[i]=0;
l=strlen(s);
for (int j=0;j<l;j++)
c[i]=c[i]*31+s[j]-'a'+1;
c[i]=c[i]*mi[10-l];
d[i]=c[i]+(mi[10-l]-1)/30*('z'-'a'+1);
p[++cnt]=(ll)c[i]-1;
p[++cnt]=(ll)d[i];
Add(a[i],i,d[i],1);
Add(b[i],i,d[i],1);
Add(lca[i],i,d[i],-2);
Add(a[i],i,c[i]-1,-1);
Add(b[i],i,c[i]-1,-1);
Add(lca[i],i,c[i]-1,2);
}
sort(p+1,p+cnt+1);
cnt=unique(p+1,p+cnt+1)-p-1;
for (int i=1;i<=edgenum;i++)
dis[i]=lower_bound(p+1,p+cnt+1,dis[i])-p;
for (int i=1;i<=Edgenum;i++)
Ask[i]=lower_bound(p+1,p+cnt+1,Ask[i])-p;
dfs(1);
for (int i=1;i<=q;i++)
printf("%lld\n",ans[i]);
}
，反正好像是二分一下答案，然后将分母乘过去，然后再去解决。
