LINK：字符串树
先说比较简单的正解。由于我没有从最简单的考虑答案的角度思考 所以...
下次还需要把所有角度都考察到。
求x~y的答案 考虑 求x~根+y~根-2*lca~根的答案。
那么问题变成了 求某个点到根的边有多少条是以当前询问为前缀的。
前缀这个问题容易想到trie树 建立前缀trie树 即 可持久化trie树即可。
还有两种考虑问题的角度。
可以直接对边建立trie树 让询问在上面跑到一个节点 那么 我们问题变成了求某个节点内的终止节点在x~y的路径上的个数。
把点赋上点权 那么树链剖分可以解决 不过线段树则需要先线段树合并一下 复杂度1e6*log+Qlog^2.
代码复杂度较高。
当然还可以离线 考虑对询问建立 trie 拿每一条边在上面跑 最后统计答案和上面的过程差不多。
这里使用的是第一种简便的方法。从某种意义上讲 第一种方法是剩下的方法正难则反的过程。
const int MAXN=100010,N=11;
int n,len=1,id,Q,L;
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];
inline void add(int x,int y)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
}
int root[MAXN],Log[MAXN],l[MAXN],d[MAXN],f[MAXN][20];
char a[MAXN][N],b[N];
struct wy
{
int ch[26];
int sum;
}t[MAXN*N];
inline void insert(int &p,int las,int d,int w)
{
p=++id;t[p]=t[las];++sum(p);
if(d==l[w]+1)return;
int cc=a[w][d]-'a';
insert(t[p].ch[cc],t[las].ch[cc],d+1,w);
}
inline void dfs(int x,int fa)
{
d[x]=d[fa]+1;f[x][0]=fa;
rep(1,Log[d[x]],i)f[x][i]=f[f[x][i-1]][i-1];
go(x)if(tn!=fa)
{
insert(root[tn],root[x],1,i>>1);
dfs(tn,x);
}
}
inline int LCA(int x,int y)
{
if(d[x]<d[y])swap(x,y);
fep(Log[d[x]],0,i)if(d[f[x][i]]>=d[y])x=f[x][i];
if(x==y)return x;
fep(Log[d[x]],0,i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
inline int ask(int p,int d)
{
if(!p)return 0;
if(d==L+1)return sum(p);
int cc=b[d]-'a';
return ask(t[p].ch[cc],d+1);
}
int main()
{
freopen("1.in","r",stdin);
gt(n);
rep(2,n,i)
{
Log[i]=Log[i>>1]+1;
int x,y;gt(x);gt(y);
gc(a[i-1]);add(x,y);add(y,x);
l[i-1]=strlen(a[i-1]+1);
}
dfs(1,0);gt(Q);
rep(1,Q,i)
{
int x,y;
gt(x);gt(y);gc(b);
int lca=LCA(x,y);L=strlen(b+1);
put(ask(root[x],1)+ask(root[y],1)-ask(root[lca],1)*2);
}
return 0;
}