https://vjudge.net/contest/579844#problem/F

1. 看到连边和没有强制在线，考虑Kruskal重构树
2. 看到判断子串，考虑AC自动机+线段树

然后要非常大胆地把两个结合起来。

然后就是大码量了。

具体总结一下流程：

1. 先建出Kruskal重构树
2. 对Kruskal重构树处理出dfn序
3. 重新对字符串进行排序
4. 对字符串建AC自动机
5. 对fail树处理出dfn序
6. 对询问操作处理出Kruskal重构树上对应区间进行差分
7. 按顺序加入每个字符串，在树状数组上进行区间加操作，树状数组维护差分
8. 对于每个询问在Trie树上跑，在对应树状数组上询问并统计答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define N 500010
struct node {int id, f; 
};
int n, m, i, j, k, T;
int a[N], a_st[N], a_ed[N], num, tot; 
int dfn[N], ed[N], p[N], qqq, f[N], op, dian[N]; 
int ans[N]; 
int u, v; 
vector<int>G[N]; 
vector<node>Q[N]; 
vector<int>s[N], t[N], S[N]; 
char str[N]; 
queue<int>q; int fa(int x) {if(f[x]==x) return x; return f[x]=fa(f[x]); 
}void dfs(int x) {if(x<=n) a[++num]=x, a_st[x]=num; for(int y :  G[x]) {dfs(y); if(!a_st[x]) a_st[x]=a_st[y]; }a_ed[x]=num; 
}struct Tree_zhuang_number_group {int n, cnt[N]; void add(int x, int y) {while(x<=n)	 {cnt[x]+=y; x+=x&-x; }}int que(int x) {int ans=0; while(x) ans+=cnt[x], x-=x&-x; return ans; }
}Bin;struct AC_auto_machine {int tot=1, nxt[N][26], fail[N]; int dfn[N], ed[N], num; vector<int>G[N]; int Trie(int u, int i, int id) {if(!s[id][i]) return u; int c=s[id][i]-'a'; if(!nxt[u][c]) nxt[u][c]=++tot; return Trie(nxt[u][c], i+1, id); }void bfs() {q.push(1); while(!q.empty()) {u=q.front(); q.pop(); for(int i=0; i<26; ++i) {if(!nxt[u][i]) continue; v=nxt[u][i]; k=fail[u]; while(k && !nxt[k][i]) k=fail[k]; if(nxt[k][i]) fail[v]=nxt[k][i]; else fail[v]=1; q.push(v); }}}void pre_dfs() {for(int i=2; i<=tot; ++i) G[fail[i]].pb(i); }void dfs(int x) {dfn[x]=++num;for(int y : G[x]) dfs(y); ed[x]=num; }void jia(int i) {Bin.add(ed[p[i]]+1, -1); Bin.add(dfn[p[i]], 1); }int que(int id) {char c; int ans=0; for(int j=1, i=0; t[id][i]; ++i) {c=t[id][i]-'a'; while(j && !nxt[j][c]) j=fail[j]; if(nxt[j][c]) j=nxt[j][c]; else j=1; ans+=Bin.que(dfn[j]); }return ans; }
}AC;signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);n=read(); for(i=1; i<=n; ++i) {scanf("%s", str+1); for(j=1; str[j]; ++j) S[i].pb(str[j]); S[i].pb(0); }qqq=read(); tot=n; for(i=1; i<=2*n; ++i) f[i]=i; while(qqq--) {op=read(); if(op==1) {u=read(); v=read(); u=fa(u); v=fa(v); if(u==v) continue; ++tot; G[tot].pb(u); G[tot].pb(v); f[u]=tot; f[v]=tot; }else {u=read(); scanf("%s", str+1); u=fa(u); ++m; dian[m]=u; for(j=1; str[j]; ++j) t[m].pb(str[j]); t[m].pb(0); }} for(i=1; i<=tot; ++i) if(fa(i)==i) G[tot+1].pb(i), f[i]=tot+1; ++tot; dfs(tot); for(i=1; i<=n; ++i) s[i]=S[a[i]]; for(i=1; i<=n; ++i) {p[i]=AC.Trie(1, 0, i); }AC.bfs(); AC.pre_dfs(); 	AC.dfs(1); Bin.n=AC.tot; for(i=1; i<=m; ++i) {Q[a_st[dian[i]]-1].pb({i, -1}); Q[a_ed[dian[i]]].pb({i, 1}); }for(i=1; i<=n; ++i) {AC.jia(i);for(node x : Q[i]) {ans[x.id]+=x.f*AC.que(x.id); }}for(i=1; i<=m; ++i) printf("%lld\n", ans[i]); return 0;
}``