题意：有N个串，给出的形式是拼接给出，对于第i行： (1,c)表示字符串i是单个字母c； （2，p，c）表示字符串i=在字符串p后面接上一个字母c。
然后给出M个提问，形式是（i，string）。问string在字符串i中出现了多少次。
思路：这类题显然是在AC自动机上乱搞。 对于询问的串建立AC自动机，BFS建立fail树；那么一个询问其实就是第i个串的位置到根的这些节点，有多少个在string节点的子树里。 即给一条链染色，然后询问一个点是子树里多少点被染色了。 为了不重不漏， 我们用回溯就可以处理了。 然后用树状数组维护DFS序下的前缀和。
具体的，对于N个串在AC自动机上跑，每跑一步对应N个字符串之一。 每跑到一个节点，就加加。 跑完子树后就减减，保证了加的部分是一条链。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
vector<pii>G[maxn],Q[maxn];
vector<int>F[maxn];
int ch[maxn][],fail[maxn],ans[maxn],tot;
int in[maxn],out[maxn],times; //dfn
char s[maxn]; int sum[maxn];
void add(int x,int val){ while(x<=times) sum[x]+=val,x+=(-x)&x;}
int query(int x){ int res=; while(x){ res+=sum[x]; x-=(-x)&x; } return res;}
int add()
{
int now=,L=strlen(s);
rep(i,,L-) {
if(!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++tot;
now=ch[now][s[i]-'a'];
} return now;
}
void build()
{
queue<int>q;
rep(i,,) if(ch[][i]) q.push(ch[][i]);
while(!q.empty()){
int u=q.front(); q.pop();
rep(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];
}
}
rep(i,,tot) F[fail[i]].push_back(i);
}
void dfs(int u)
{
in[u]=++times;
for(int i=;i<F[u].size();i++) dfs(F[u][i]);
out[u]=times;
}
void dfs(int u,int now) //u是位置，now是id
{
add(in[u],);
for(int i=;i<Q[now].size();i++){
pii t=Q[now][i];
ans[t.second]=query(out[t.first])-query(in[t.first]-);
}
for(int i=;i<G[now].size();i++){
pii t=G[now][i];
dfs(ch[u][t.first],t.second);
}
add(in[u],-);
}
int main()
{
int N,M,opt,p;
scanf("%d",&N);
rep(i,,N) {
scanf("%d",&opt);
if(opt==) p=;
else scanf("%d",&p);
scanf("%s",s);
G[p].pb(pii(s[]-'a',i));
}
scanf("%d",&M);
rep(i,,M) {
scanf("%d%s",&p,s);
Q[p].pb(pii(add(),i));
}
build();
dfs();
dfs(,);
rep(i,,M) printf("%d\n",ans[i]);
return ;
}