哈哈哈看我(O(|S|log^2|S|))干(2e6)
发现如果不是动态询问就是一道板子题，我们直接对所有询问串建(AC)自动机，之后跑一跑就成子树数颜色了
但是现在总不能动态数颜色啊
但是我们还是可以离线，之后我们现在只需要数时间小于当前询问的颜色就好了
又是树上的问题我们考虑直接(dsu on tree)
发现如果当前点没有询问，并且也不是重儿子，我们就没有什么必要统计这颗子树的信息了
之后大力(dsu)就好了
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define re register
#define maxn 2000005
#define LL long long
#define mp std::make_pair
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt;}e[maxn];
typedef std::pair<int,int> pii;
std::vector<int> p[maxn];
std::vector<pii> a[maxn];
int n,m,cnt,top,Son,num;
char S[maxn];
int pos[100005],sum[maxn],vis[maxn],son[maxn],st[maxn];
int ch[maxn][26],fail[maxn],head[maxn];
int Ans[100005];
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
inline void ins(int o) {
scanf("%s",S+1);int len=strlen(S+1);
int now=0;
for(re int i=1;i<=len;i++) {
if(!ch[now][S[i]-'a']) ch[now][S[i]-'a']=++cnt;
now=ch[now][S[i]-'a'];
}
pos[o]=now;
}
inline void Build() {
std::queue<int> q;
for(re int i=0;i<26;i++) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty()) {
int k=q.front();q.pop();
for(re int i=0;i<26;i++)
if(ch[k][i]) fail[ch[k][i]]=ch[fail[k]][i],q.push(ch[k][i]);
else ch[k][i]=ch[fail[k]][i];
}
}
inline void check(int o) {
scanf("%s",S+1);int len=strlen(S+1);
int now=0;
for(re int i=1;i<=len;i++) {
now=ch[now][S[i]-'a'];
p[now].push_back(o);
}
}
void dfs1(int x) {
sum[x]=1;int maxx=-1;
for(re int i=head[x];i;i=e[i].nxt) {
dfs1(e[i].v);
sum[x]+=sum[e[i].v];
if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[x]=e[i].v;
}
}
void calc(int x) {
for(re int i=0;i<p[x].size();i++) {
if(vis[p[x][i]]) continue;
vis[p[x][i]]=1;st[++top]=p[x][i];
}
for(re int i=head[x];i;i=e[i].nxt) {
if(e[i].v==Son) continue;
calc(e[i].v);
}
}
void dfs(int x,int k) {
for(re int i=head[x];i;i=e[i].nxt)
if(son[x]!=e[i].v) dfs(e[i].v,0);
if(son[x]!=-1) dfs(son[x],1);
if(k||a[x].size()>0)
Son=son[x],calc(x),Son=0;
if(a[x].size()>0) {
std::sort(st+1,st+top+1);
int now=1;
for(re int i=0;i<a[x].size();i++) {
while(now<=top&&st[now]<=a[x][i].first)
now++;
Ans[a[x][i].second]=now-1;
}
}
if(!k) while(top) vis[st[top--]]=0;
}
int main() {
n=read();
for(re int i=1;i<=n;i++) ins(i);
Build();
m=read();
int opt,x,tot=0,qnum=0;
for(re int i=1;i<=cnt;i++)
add(fail[i],i);
while(m--) {
opt=read();++tot;
if(opt==1) check(tot);
else {
++qnum;x=read();
a[pos[x]].push_back(mp(tot,qnum));
}
}
for(re int i=1;i<=n;i++)
std::sort(a[pos[i]].begin(),a[pos[i]].end());
memset(son,-1,sizeof(son));
dfs1(0);dfs(0,1);
for(re int i=1;i<=qnum;i++)
printf("%d
",Ans[i]);
return 0;
}