CWOI 字符串专题

#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;
}