思路
每次询问 \(u,v\) 的简单路径上有多少个字符串以 \(s\) 为前缀，不难想到用 trie 树去维护。而普通的 trie 只能查询所有字符串中产生的答案，对于这类区间询问，就要用到可持久化 trie 树了。不会右转可持久化 trie 树模板题。
\(u,v\) 的简单路径上编号不连续，非要把它拉到序列上可以树剖，麻烦了。树上两点间的查询还有一个简单思路：求出他们的 lca 为 \(p\)，那么答案就是 \(ans_u+ans_v-2\times ans_p\)。其中 \(ans_i\) 表示 \(i\) 到根节点的路径上，有多少个字符串以 \(s\) 为前缀。这样，我们就只需要解决 \(i\) 到根节点的问题了。
首先把边上的字符串转化到点上，因为每个点只有一个父亲，因此 \(fa \to u\) 这条路径上的字符串就可以记为 \(s_u\) 。然后按照 dfs 序建立每个点 trie 树的 \(root\) （可持久化），每次从这个点的父亲的 \(root\) 继承过来，那么下次访问这个点时就只会统计他到根节点上的答案了。算答案可以记一个 \(sum_p\) 表示 trie 树上经过了 \(p\) 这个点的字符串有多少个。与普通 trie 不同的是，他要记录当前点到根节点的所有答案，因此在插入时 \(sum_p\) 不能单纯地 \(+1\)，而是用前缀和的形式要继承它父亲的答案，即 \(sum_p=sum_{pre}+1\)。查询如果发现一个点 \(p\) 值为 \(0\)，那就说明没有 \(s\) 这个字符串，return 0 就行。否则一直走完 \(s\)，最后 return sum[p]。
code
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define mkp make_pair
using namespace std;
typedef pair<int,string>pii;
const int N=1e5+5;
int n,m,k,cnt,tot,dep[N];
int f[25][N],root[N];
vector<pii>e[N];
int tr[N*10][28],sum[N*10];
int work(char c){
return c-'a'+1;
}
void insert(int pre,int p,string s){
for(int i=0;i<s.size();++i){
int u=work(s[i]);
if(pre)for(int j=1;j<=26;++j)if(j!=u)tr[p][j]=tr[pre][j];//继承
tr[p][u]=++cnt;
p=tr[p][u];
pre=tr[pre][u];
sum[p]=sum[pre]+1;//更新前缀和
}
}
int query(int p,string s){
for(int i=0;i<s.size();++i){
int u=work(s[i]);
if(!tr[p][u])return 0;//没找到返回0
p=tr[p][u];
}
return sum[p];
}
void dfs(int u,int fa){
f[0][u]=fa;
dep[u]=dep[fa]+1;
for(int i=1;i<=20;++i)f[i][u]=f[i-1][f[i-1][u]];
for(auto tmp:e[u]){
int v=tmp.first;
string s=tmp.second;
if(v==fa)continue;
root[v]=++cnt;
insert(root[u],root[v],s);//每次继承它父亲的trie
dfs(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;--i)if(dep[f[i][x]]>=dep[y])x=f[i][x];
if(x==y)return x;
for(int i=20;i>=0;--i)
if(f[i][x]!=f[i][y]){
x=f[i][x];
y=f[i][y];
}
return f[0][x];
}
int main(){
cin>>n;
for(int i=1;i<n;++i){
int a,b;
string s;
cin>>a>>b>>s;
e[a].pb(mkp(b,s));e[b].pb(mkp(a,s));
}
dfs(1,0);
int q;
cin>>q;
while(q--){
int u,v;string s;
cin>>u>>v>>s;
cout<<query(root[u],s)+query(root[v],s)-2*query(root[lca(u,v)],s)<<endl;
}
return 0;
}