题目
题解：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int trie[maxn][26];//trie[i][j]表示编号为i的结点 的代表字母j的子结点
int tot;//字典树结点个数
int fail[maxn];//fail[i]指向 根结点到结点i组成的字符串的最大后缀 的结点，如 /* 0/ \1(s) 4(h)/ \2(h) 5(e)/3(e) 3指向5，2指向4*/
void get_fail(){//bfs更新fail数组queue<int> q;for(int i = 0; i < 26; i++){if(trie[0][i]){fail[trie[0][i]] = 0;//第二层结点fail指向0，入队q.push(trie[0][i]);} }while(!q.empty()){int u = q.front();q.pop();for(int i = 0; i < 26; i++){int v = trie[u][i];//子结点if(v){//子结点不为空int t = fail[u];fail[v] = trie[t][i];//fail指向 父结点fail指向的结点 的子结点q.push(v);}else{int t = fail[u];trie[u][i] = trie[t][i];//改变字典树，让u fail指向的结点 的子结点 成为u的子结点（即在u结点失配时，可以移动到失配指针指向的结点的下一个结点，继续匹配）}}}
}int t[maxn];
int n;
int lowbit(int x){return x & -x;}
void add(int x, int k){for(int i = x; i <= n; i += lowbit(i)){t[i] += k;}
}
int ask(int x){int res = 0;for(int i = x; i; i -= lowbit(i)){res += t[i];}return res;
}void solve(){cin >> n;for(int i = 0; i <= n; i++){//从0开始！！！t[i] = 0;fail[i] = 0;for(int j = 0; j < 26; j++){trie[i][j] = 0;}}for(int i = 1; i < n; i++){int j;cin >> j;j--;char ch;cin >> ch;trie[j][ch - 'a'] = i;}get_fail();vector<int> L(n + 1), R(n + 1);vector<vector<int>> G(n + 1);for(int i = 1; i < n; i++){G[fail[i]].push_back(i);// cout << i << ' ' << fail[i] << '\n';}int tot = 0;auto dfs = [&](auto self, int u) -> void {L[u] = ++tot;for(auto v : G[u]){self(self, v);}R[u] = tot;};dfs(dfs, 0);int m;cin >> m;for(int i = 1; i <= m; i++){int op, k, x;cin >> op;if(op == 1){cin >> k;int l = n, r = 1;vector<pair<int, int>> vec;for(int j = 1; j <= k; j++){cin >> x;x--;// if(x == 0) continue;vec.push_back({L[x], R[x]});}sort(vec.begin(), vec.end());for(int i = 0; i < vec.size(); ){add(vec[i].first, 1);add(vec[i].second + 1, -1);int j = i + 1;while(j < vec.size() && vec[j].second <= vec[i].second){j++;}i = j;}}else{cin >> x;x--;cout << ask(L[x]) << '\n';}}
}int main(){ios::sync_with_stdio(0);cin.tie(0);int T = 1;cin >> T;while(T--){solve();}return 0;
}
