ac

main.cpp

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <cstring>
#include <queue>
#include <bits/stdc++.h>
#include <cstdio>
#include <stdio.h>
using namespace std;
const int N = (int)4e3+10;
const int SZ = N * 80;
int n,m;
char strc[N];
int tot, tr[SZ][26];
int fail[SZ];
int mtn[N];
//int trID[N],reTrID[N];
//int treeCnt=0;
bool vis[N];
int fa[N],ans[N];
struct Node{
  Node(int v,int w): v(v) , w(w) {};
  int v,w;
};
vector<Node>match[N];
vector<Node>name[N];
vector<Node>vec[N];
vector<Node>que[N];

int findfa(int i){
  return fa[i] = fa[i] == i ? i : findfa(fa[i]);
}
void init() {
  memset(fail, 0, sizeof(fail));
  memset(tr, 0, sizeof(tr));
  tot = 0;
}
void cinsert(const char *s,int du,int quei) {
  int charu = 0;
  for (int i = 0; s[i]; i++) {
    if (!tr[charu][s[i] - 'a']) tr[charu][s[i] - 'a'] = ++tot;
    charu = tr[charu][s[i] - 'a'];
  }
  name[charu].push_back(Node(du,quei));
}
void cbuild() {
  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 query(int t,int charu,int tu) {
  charu = tr[charu][t];
  for (int j = charu; j; j = fail[j]){
    for(int i = 0;i < name[charu].size();i++){
      match[name[charu][i].v].push_back(Node(tu,name[charu][i].w));
    }
  }
  return charu;
}
void LCA(int u,int charu){
  fa[u] = u;
  for(int i =0;i < vec[u].size();i++){
    Node cur = vec[u][i];
    int v=cur.v,c=cur.w;
    int charv = query(c,charu,v);
    LCA(v,charv);
    fa[v] = u;
  }
  vis[u] = true;
  for(int i = 0;i < match[u].size();i++)
  {
    int v = match[u][i];
    int qidx=matchq[u][i];
    if(vis[v] && findfa(u)==v)ans[qidx]++;
  }
}
int main(){
  while(cin>>n){
    init();
    for(int i=1;i<=n;++i){
      int op,j;
      char ch;
      scanf("%d",&op);
      //emplace_back
      if(op==1)scanf(" %c",&ch),vec[0].push_back(Node(i,ch-'a'));
      else scanf("%d %c",&j,&ch),vec[j].push_back(Node(i,ch-'a'));
    }
    //dfs_get_tree_id(0);
    cin>>m;
    for(int quei=1;quei <= m;quei++){
      int u;
      scanf("%d%s",&u,strc);
      cinsert(strc,u,quei);
      mtn[quei]=u;
    }
    cbuild();
    LCA(0,0);
    for(int i =0;i < m;i++)cout << ans[i+1] << endl;
  }
  return 0;
}

//void dfs_get_tree_id(int u){
//  for(int i =0;i < vec[u].size();i++){
//    Node cur = vec[u][i];
//    int v=cur.v;
//    trID[u]=treeCnt;
//    reTrID[treeCnt]=u;
//    treeCnt++;
//    dfs_get_tree_id(v);
//  }
//}