特别鸣神犇 fcwww 替我调出了无数个错误（没他的话我都快自闭了），祝大佬省选rp++
板子题，给我写了一天QAQ......
用 LCT 维护后缀树，暴力更新用 LCT 区间更新链即可
其实，在计算本职不同子串的时候很多网友算的都有点麻烦
不管实在后缀自动机，还是广义后缀自动机中，动态更新本质不同子串数量用最后新加的点更新即可，和其他点是无关的.
Code:
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define setIO(s) freopen(s".in","r",stdin) ,freopen(s".out","w",stdout)
#define maxn 800000
#define N 10
#define ll long long
using namespace std;
char str[maxn];
long long cur_ans;
struct Link_Cut_Tree{
int ch[maxn][2],f[maxn],tag[maxn],sta[maxn],val[maxn];
int get(int x) {return ch[f[x]][1]==x; }
int which(int x){ return ch[f[x]][1]==x;}
int isRoot(int x){ return !(ch[f[x]][1]==x||ch[f[x]][0]==x);}
int lson(int x){ return ch[x][0];}
int rson(int x){return ch[x][1];}
void add(int x,int delta){if(!x)return;val[x]+=delta,tag[x]+=delta;}
void pushdown(int x){if(tag[x]) add(lson(x),tag[x]),add(rson(x),tag[x]),tag[x]=0;}
void rotate(int x){
int old=f[x],fold=f[old],which=get(x);
if(!isRoot(old)) ch[fold][ch[fold][1]==old]=x;
ch[old][which]=ch[x][which^1],f[ch[old][which]]=old;
ch[x][which^1]=old,f[old]=x,f[x]=fold;
}
void splay(int x){
int v=0,u=x;
sta[++v]=u;
while(!isRoot(u)) sta[++v]=f[u],u=f[u];
while(v) pushdown(sta[v--]);
u=f[u];
for(int fa;(fa=f[x])!=u && x;rotate(x))
if(f[fa]!=u) rotate(get(fa)==get(x)?fa:x);
}
void Access(int x){
for(int y=0;x;y=x,x=f[x])
splay(x),ch[x][1]=y;
}
void link(int a,int b){
Access(a),splay(a),add(a,val[b]),f[b]=a;
}
void cut(int b){
Access(b),splay(b);
add(lson(b),-val[b]),f[lson(b)]=ch[b][0]=0;
}
}tree;
struct SAM{
int ch[maxn][10],f[maxn],dis[maxn];
int tot,last;
void init(){ last=tot=1; }
int ins(int c){
int p=last,np=++tot; last=np; dis[np]=dis[p]+1;tree.val[np]=tree.tag[np]=1;
while(p&&!ch[p][c])ch[p][c]=np,p=f[p];
if(!p) f[np]=1,tree.link(1,np);
else{
int q=ch[p][c],nq;
if(dis[q]==dis[p]+1)f[np]=q,tree.link(q,np);
else{
nq=++tot;
dis[nq]=dis[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
f[nq]=f[q];
tree.link(f[q],nq),tree.cut(q),tree.link(nq,q),tree.link(nq,np);
f[q]=f[np]=nq;
while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p];
}
}
cur_ans+=dis[np] - dis[f[np]];
return np;
}
}sam;
struct Node{
int u,c;
Node(int u=0,int c=0):u(u),c(c){}
};
queue<int>Q;
vector<int>mark;
vector<Node>G[maxn];
int idx[maxn];
void DFS(int u,int fa){
int k=G[u].size();
for(int i=0;i<k;++i){
Node j=G[u][i];
if(j.u==fa) continue;
sam.last=idx[u],idx[j.u]=sam.ins(j.c);
DFS(j.u,u);
}
G[u].clear();
}
void build_Tree(int n,int st){
for(int i=1;i<n;++i) {
int u,v;
char c[10];
scanf("%d%d",&u,&v);
scanf("%s",c);
G[u].push_back(Node(v,c[0]-'a'));
G[v].push_back(Node(u,c[0]-'a'));
}
DFS(st,0);
}
int main(){
//setIO("input");
int lll,n,m;
scanf("%d",&lll); sam.init(),idx[1] = 1; scanf("%d",&n);
build_Tree(n,1); scanf("%d",&m); for(int i=1;i<=m;++i) {
int opt_idx,a,b;
scanf("%d",&opt_idx);
if(opt_idx==1) printf("%lld\n",cur_ans);
if(opt_idx==2) {
scanf("%d%d",&a,&b);
build_Tree(b,a);
}
if(opt_idx==3) {
scanf("%s",str);
a=strlen(str);
b=1;
bool flag = 0;
for(int j=0;j<a;++j) {
b=sam.ch[b][str[j]-'a'];
if(!b) flag = 1;
}
if(flag) printf("0\n");
else {
tree.Access(b);
tree.splay(b);
printf("%d\n",tree.val[b]);
}
}
}
return 0;
}