A - Indie Album
考虑离线，对询问串跑 AC 自动机，建出 fail 树。再把题目中那个版本继承关系建成一棵树，在这棵树上 dfs，进入一个点的时候在 fail 树上单点加，走的时候减掉，维护子树求和即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct edge{
int v,nxt;
}e[400005];
int tot,head[400005];
void add(int u,int v){
e[++tot]=(edge){v,head[u]},head[u]=tot;
}
int I,ch[400005][28],fail[400005];
void build(){
queue<int>q;
for(int i=0;i<26;i++)if(ch[0][i])q.push(ch[0][i]);
while(!q.empty()){
int u=q.front();q.pop();add(fail[u],u);
for(int i=0;i<26;i++){
if(ch[u][i])fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
else ch[u][i]=ch[fail[u]][i];
}
}
}
int cur,dfn[400005],rnk[400005],siz[400005];
vector<int>g[400005],t[400005];
struct BIT{
int c[400005];
void add(int x,int v){
for(;x<=cur;x+=x&-x)c[x]+=v;
}
void add(int l,int r,int v){
add(l,v),add(r+1,-v);
}
int ask(int x){
int res=0;
for(;x;x-=x&-x)res+=c[x];
return res;
}
int ask(int l,int r){
return ask(r)-ask(l-1);
}
}Tr;
int p[400005],ans[400005],endpos[400005];
void dfs1(int u){
dfn[u]=++cur,rnk[cur]=u,siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
dfs1(v);siz[u]+=siz[v];
}
}
void dfs2(int u){
Tr.add(dfn[p[u]],1);
for(auto x:t[u])ans[x]=Tr.ask(dfn[endpos[x]],dfn[endpos[x]]+siz[endpos[x]]-1);
for(auto v:g[u])dfs2(v);
Tr.add(dfn[p[u]],-1);
}
int op[400005];int x[400005],q[400005];char c[400005][5];string s[400005];
signed main(){
int n=read();
for(int i=1;i<=n;i++){
op[i]=read();
if(op[i]==1)scanf("%s",c[i]),g[0].push_back(i);
else x[i]=read(),scanf("%s",c[i]),g[x[i]].push_back(i);
}
int m=read();
for(int i=1;i<=m;i++){
q[i]=read();cin>>s[i];
}
for(int i=1;i<=m;i++){
int u=0;
for(int j=0;j<(int)s[i].size();j++){
if(!ch[u][s[i][j]-'a'])ch[u][s[i][j]-'a']=++I;
u=ch[u][s[i][j]-'a'];
}
endpos[i]=u,t[q[i]].push_back(i);
}
build();
for(int i=1;i<=n;i++){
if(op[i]==1)p[i]=ch[0][c[i][0]-'a'];
else p[i]=ch[p[x[i]]][c[i][0]-'a'];
}
dfs1(0);dfs2(0);
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}