有n次操作，格式为1 c或2 j c，分别表示新建一个为c的字符串，和在第j次操作得到的串后接上c后新建一个字符串。
接着是m次询问，每次询问版本i的串中，t的出现次数。
m次询问，每次询问版本i的字符串中，t的出现次数。
如果暴力建字符串肯定存不下。
考虑a aa aaa aaaa aaaaa...这种情况，必爆。
现在考虑优化操作2。
称每种操作2所修改的字符串编号为它的父亲。
每个由操作2得到的字符串的父亲节点唯一。
那么可以先对所有字符串建一颗字符树。
然后把询问离线，即每种字符串i对应的询问集中处理。
然后，先对所有t串建AC自动机。
然后在字符树上搜索，维护当前节点到根节点的路径。
为了方便操作，加一个巨大的根节点，编号为0。
往下搜，就把对应下一个节点的AC自动机上的节点编号塞入路径。
回溯的时候，把路径的最后一个节点编号退出即可。
然后，对当前路径，依次处理询问。
加入路径的时候，在fail树上让对应点权+1。
处理单个询问的t串的时候，询问子树和就可以。
这样就可以用线段树维护fail树的dfs序来处理子树和。
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+100;
vector<int> gg[maxn];
char a[maxn];
string t[maxn];
vector<int> qq[maxn];
int n,m,q;
int tr[maxn][26],fail[maxn],sz[maxn],tot;
vector<int> g[maxn];
int ed[maxn];
int dfn[maxn],cnt;
int insert (string s) {
int u=0;
for (char i:s) {
if (!tr[u][i-‘a‘]) tr[u][i-‘a‘]=++tot;
u=tr[u][i-‘a‘];
}
return u;
}
void build () {
queue<int> q;
for (int i=0;i<26;i++) {
if (tr[0][i]) {
q.push(tr[0][i]);
}
}
while (q.size()) {
int u=q.front();
q.pop();
for (int i=0;i<26;i++) {
if (tr[u][i]) {
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}
else {
tr[u][i]=tr[fail[u]][i];
}
}
}
}
int c[maxn<<2];
void up (int i,int l,int r,int p,int v) {
if (l==p&&r==p) {
c[i]+=v;
return;
}
int mid=(l+r)>>1;
if (p<=mid) up(i<<1,l,mid,p,v);
if (p>mid) up(i<<1|1,mid+1,r,p,v);
c[i]=c[i<<1]+c[i<<1|1];
}
int query (int i,int l,int r,int L,int R) {
if (l>=L&&r<=R) return c[i];
int mid=(l+r)>>1;
int ans=0;
if (L<=mid) ans+=query(i<<1,l,mid,L,R);
if (R>mid) ans+=query(i<<1|1,mid+1,r,L,R);
return ans;
}
void dfs1 (int u) {
sz[u]=1;
dfn[u]=++cnt;
for (int v:g[u]) {
dfs1(v);
sz[u]+=sz[v];
}
}
int ans[maxn];
void dfs2 (int u,int uu) {
for (int v:qq[u]) ans[v]=query(1,1,cnt,dfn[ed[v]],dfn[ed[v]]+sz[ed[v]]-1);
for (int v:gg[u]) {
up(1,1,cnt,dfn[tr[uu][a[v]-‘a‘]],1);
dfs2(v,tr[uu][a[v]-‘a‘]);
up(1,1,cnt,dfn[tr[uu][a[v]-‘a‘]],-1);
}
}
int main () {
ios::sync_with_stdio(false);
cin>>n;
while (n--) {
int op;
cin>>op;
if (op==1) {
m++;
gg[0].push_back(m);
char ch;
cin>>ch;
a[m]=ch;
}
else {
int x;
char ch;
cin>>x>>ch;
m++;
gg[x].push_back(m);
a[m]=ch;
}
}
cin>>q;
for (int i=1;i<=q;i++) {
int x;
cin>>x>>t[i];
qq[x].push_back(i);
ed[i]=insert(t[i]);
}
build();
for (int i=1;i<=tot;i++) g[fail[i]].push_back(i);
dfs1(0);
dfs2(0,0);
for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
}