思路

每次询问 $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;
}