Description

DQS的自家阳台上种着一棵颗粒饱满、颜色纯正的trie。

DQS的trie非常的奇特，它初始有n0个节点，n0-1条边，每条边上有一个字符。并且，它拥有极强的生长力：某个i时刻，某个节点就会新生长出一颗子树，它拥有si个节点且节点之间的边上有一个字符，并且新生长出来的子树也是一个树结构。然而因为是新长出来的，根据生活常识可知si必定不会大于i时刻之前的树的大小。

DQS定义trie的子串为从根节点（1号节点）往下走到所有节点所构成的字符串的所有的后缀。DQS身为一个单身doge，常常取出其中一个子串送给妹子，然而他并不希望送给妹子两个相同的子串，所以他非常关心当前trie的本质不同的子串数目。

DQS有时还会去商店购买子串，若他在商店看上某个子串，他希望得知这个子串是否在自家阳台的trie上已经出现，若出现则出现了多少次。如果出现了，他就可以直接回家取trie上的子串辣！

然而DQS身为一个蒟蒻，看着自家阳台的trie树一天天在长大，他被如此众多的节点弄得眼花缭乱，于是他找到了IOI2016Au的你。他会告诉你自家trie树的成长历程，他希望你能够对于每一次询问都做出正确回复。

Input

第一行输入一个整数id，代表测试点编号。

接下来一行输入一个整数n0，表示初始树的大小。

接下来n0-1行，每行两个整数u,v和一个字符c，表示u号节点和v号节点之间有一条边，边上的字母为c。

接下来输入m表示有m组操作。

对于每一组，第一行输入一个整数opt。

若opt=1，则是一组询问，询问当前trie的本质不同的子串数目是多少。

若opt=2，则后面跟两个整数rt,si，表示以点rt为根向下长出一个子树，大小为si。

接下来si-1行，每行两个整数u,v和一个字符c，表示u号节点和v号节点之间有一条边，边上的字母为c。若长出子树之前当前树的大小是n，则这si-1点的编号分别为n+1,n+2…n+si-1。

若opt=3，则是一组询问，后面输入一个字符串S，询问字符串S在当前trie中的出现次数。

Solution

比较直观

操作 \(1\) ,就是维护 \(\sum len[x]-len[fa[x]]\) ,改变父亲关系时加减一下就好了

然而在加入一个 \(nt\) 的时候,把式子列出来发现直接抵消了,\(QAQ\)

实际上维护一下 \(cur\) 的变化就好了

操作 \(2,3\) 和 \(substring\) 一题类似, \(LCT\) 维护链加法就好了

#include
    
     using namespace std;typedef long long ll;template
     
      void gi(T &x){    int f;char c;    for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;    for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;}const int N=2e5+10;namespace lct{    int fa[N],ch[N][2],w[N],la[N];    inline bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}    inline void mark(int x,int t){la[x]+=t;w[x]+=t;}    inline void pushdown(int x){        if(!la[x])return ;       mark(ch[x][0],la[x]);mark(ch[x][1],la[x]);la[x]=0;    }    inline void rotate(int x){        int y=fa[x];bool t=ch[y][1]==x;        ch[y][t]=ch[x][!t];fa[ch[y][t]]=y;        ch[x][!t]=y;fa[x]=fa[y];        if(!isrt(y))ch[fa[y]][ch[fa[y]][1]==y]=x;        fa[y]=x;    }    inline void Push(int x){        if(!isrt(x))Push(fa[x]);        pushdown(x);    }    inline void splay(int x){        Push(x);        while(!isrt(x)){            int y=fa[x],p=fa[y];            if(isrt(y))rotate(x);            else if((ch[p][0]==y)==(ch[y][0]==x))rotate(y),rotate(x);            else rotate(x),rotate(x);        }    }    inline void access(int x){        int y=0;        while(x)splay(x),ch[x][1]=y,x=fa[y=x];    }    inline void link(int x,int y){        fa[x]=y;access(y);splay(y);splay(x);mark(y,w[x]);    }    inline void cut(int x){        access(x);splay(x);mark(ch[x][0],-w[x]);ch[x][0]=fa[ch[x][0]]=0;    }    inline int qry(int x){splay(x);return w[x];}}int n,Q,head[N],nxt[N*2],to[N*2],num=0,c[N],las[N],cnt=1,cur;ll ans=0;int ch[N][26],fa[N],len[N];char s[N];inline void link(int x,int y,int z){    nxt[++num]=head[x];to[num]=y;head[x]=num;c[num]=z;    nxt[++num]=head[y];to[num]=x;head[y]=num;c[num]=z;}inline void ins(int c,int p){    cur=++cnt;len[cur]=len[p]+1;lct::w[cur]=1;    for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;    if(!p)fa[cur]=1,lct::link(cur,1);    else{        int q=ch[p][c];        if(len[p]+1==len[q])fa[cur]=q,lct::link(cur,q);        else{            int nt=++cnt;len[nt]=len[p]+1;            memcpy(ch[nt],ch[q],sizeof(ch[q]));            lct::cut(q);lct::link(nt,fa[q]);lct::link(q,nt);lct::link(cur,nt);            fa[nt]=fa[q];fa[q]=fa[cur]=nt;            for(;p && ch[p][c]==q;p=fa[p])ch[p][c]=nt;        }    }    ans+=len[cur]-len[fa[cur]];}inline void bfs(int S){    queue
      
       Q;Q.push(S);    while(!Q.empty()){        int x=Q.front();Q.pop();        for(int i=head[x],u;i;i=nxt[i]){            if(las[u=to[i]])continue;            ins(c[i],las[x]);las[u]=cur;Q.push(u);        }    }}inline int solve(){    scanf("%s",s+1);    int le=strlen(s+1),p=1;    for(int i=1;i<=le;i++){        int c=s[i]-'a';        if(ch[p][c])p=ch[p][c];        else return 0;    }    return lct::qry(p);}int main(){  freopen("pp.in","r",stdin);  freopen("pp.out","w",stdout);  gi(n);gi(n);  int x,y,op,p,q;char ch[2];  for(int i=1;i