Description

DQS的自家阳台上种着一棵颗粒饱满、颜色纯正的trie。 DQS的trie非常的奇特，它初始有$n_0$个节点，$n_0-1$条边，每条边上有一个字符。并且，它拥有极强的生长力：某个i时刻，某个节点就会新生长出一颗子树，它拥有$s_i$个节点且节点之间的边上有一个字符，并且新生长出来的子树也是一个树结构。然而因为是新长出来的，根据生活常识可知$s_i$必定不会大于i时刻之前的树的大小。 DQS定义trie的子串为从根节点（$1$号节点）往下走到所有节点所构成的字符串的所有的后缀。DQS身为一个单身doge，常常取出其中一个子串送给妹子，然而他并不希望送给妹子两个相同的子串，所以他非常关心当前trie的本质不同的子串数目。 DQS有时还会去商店购买子串，若他在商店看上某个子串，他希望得知这个子串是否在自家阳台的trie上已经出现，若出现则出现了多少次。如果出现了，他就可以直接回家取trie上的子串辣！ 然而DQS身为一个蒟蒻，看着自家阳台的trie树一天天在长大，他被如此众多的节点弄得眼花缭乱，于是他找到了IOI2016Au的你。他会告诉你自家trie树的成长历程，他希望你能够对于每一次询问都做出正确回复。

Solution

对于询问本质不同的子串数目，可以在构建后缀自动机的时候求出

对于询问子串出现的次数，相当于询问该子串对应点在parent树上子树和，其中非复制而来的点权值为1

又因为会有断边操作，所以用LCT维护子树和

数据：链接：https://pan.baidu.com/s/11daDdDrCPJYgwBWJPIgjog  提取码：bzsv

#include<iostream>
#include<cstdio>
using namespace std;
namespace LCT
{
    int tag[200005],tag2[200005],rev[200005],fa[200005],tree[200005][2],v[200005],top,st[200005];
    void pushup(int x)
    {
        tag[x]=tag[tree[x][0]]+tag[tree[x][1]]+tag2[x]+v[x];
    }
    void pushdown(int x)
    {
        if(rev[x])
        {
            if(tree[x][0])
            {
                rev[tree[x][0]]^=1;
                swap(tree[tree[x][0]][0],tree[tree[x][0]][1]);
            }
            if(tree[x][1])
            {
                rev[tree[x][1]]^=1;
                swap(tree[tree[x][1]][0],tree[tree[x][1]][1]);
            }
            rev[x]=0;
        }
    }
    int getson(int x)
    {
        return tree[fa[x]][1]==x;
    }
    int nroot(int x)
    {
        return tree[fa[x]][0]==x||tree[fa[x]][1]==x;
    }
    void rotate(int x)
    {
        int y=fa[x],z=fa[y],b=getson(x),c=getson(y),a=tree[x][!b];
        if(nroot(y))
        {
            tree[z][c]=x;
        }
        fa[x]=z;
        tree[x][!b]=y;
        fa[y]=x;
        tree[y][b]=a;
        if(a)
        {
            fa[a]=y;
        }
        pushup(y);
        pushup(x);
    }
    void splay(int x)
    {
        int top=0;
        st[++top]=x;
        for(int i=x;nroot(i);i=fa[i])
        {
            st[++top]=fa[i];
        }
        while(top)
        {
            pushdown(st[top--]);
        }
        while(nroot(x))
        {
            int y=fa[x];
            if(nroot(y))
            {
                getson(x)^getson(y)?rotate(x):rotate(y);
            }
            rotate(x);
        }
    }
    void access(int x)
    {
        for(int y=0;x;x=fa[y=x])
        {
            splay(x);
            tag2[x]+=tag[tree[x][1]]-tag[y];
            tree[x][1]=y;
            pushup(x);
        }
    }
    void makeroot(int x)
    {
        access(x);
        splay(x);
        rev[x]^=1;
        swap(tree[x][0],tree[x][1]);
    }
    void split(int x,int y)
    {
        makeroot(x);
        access(y);
        splay(y);
    }
    void link(int x,int y)
    {
        split(x,y);
        fa[x]=y;
        tag2[y]+=tag[x];
        pushup(y);
    }
    void cut(int x,int y)
    {
        split(x,y);
        tree[y][0]=fa[x]=0;
        pushup(y);
    }
}
int id,n0,tot,head[100005],m,rt,s,vst[100005],tim,cnt=1,pos[200005];
long long ans;
char str[100005];
struct Edge
{
    int to,nxt,w;
}edge[200005];
struct SAM
{
    int ch[5],fa,len;
}sam[200005];
inline int read()
{
    int w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+ch-'0';
        ch=getchar();
    }
    return w*f;
}
int insert(int las,int c)
{
    int p=las,np=++cnt;
    sam[np].len=sam[p].len+1;
    for(;p&&!sam[p].ch[c];p=sam[p].fa)
    {
        sam[p].ch[c]=np;
    }
    if(!p)
    {
        sam[np].fa=1;
    }
    else
    {
        int q=sam[p].ch[c];
        if(sam[q].len==sam[p].len+1)
        {
            sam[np].fa=q;
        }
        else
        {
            int nq=++cnt;
            sam[nq]=sam[q];
            LCT::link(nq,sam[nq].fa);
            sam[nq].len=sam[p].len+1;
            LCT::cut(q,sam[q].fa);
            sam[q].fa=sam[np].fa=nq;
            LCT::link(q,nq);
            for(;p&&sam[p].ch[c]==q;p=sam[p].fa)
            {
                sam[p].ch[c]=nq;
            }
        }
    }
    LCT::tag[np]=LCT::v[np]=1;
    LCT::link(np,sam[np].fa);
    ans+=sam[np].len-sam[sam[np].fa].len;
    return np;
}
void dfs(int k,int f)
{
    for(int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v!=f&&vst[v]==tim)
        {
            pos[v]=insert(pos[k],edge[i].w);
            dfs(v,k);
        }
    }
}
int main()
{
    id=read();
    n0=read();
    for(int i=1;i<n0;i++)
    {
        int u=read(),v=read();
        char c;
        cin>>c;
        edge[++tot]=(Edge){v,head[u],c-'a'};
        head[u]=tot;
        edge[++tot]=(Edge){u,head[v],c-'a'};
        head[v]=tot;
    }
    pos[1]=1;
    dfs(1,0);
    m=read();
    for(int i=1;i<=m;i++)
    {
        int opt=read();
        if(opt==1)
        {
            printf("%lld\n",ans);
        }
        else if(opt==2)
        {
            ++tim;
            rt=read();
            s=read();
            for(int j=1;j<s;j++)
            {
                int u=read(),v=read();
                char c;
                cin>>c;
                edge[++tot]=(Edge){v,head[u],c-'a'};
                head[u]=tot;
                edge[++tot]=(Edge){u,head[v],c-'a'};
                head[v]=tot;
                vst[u]=vst[v]=tim;
            }
            dfs(rt,0);
        }
        else
        {
            int p=1;
            scanf("%s",str);
            for(int j=0;str[j];j++)
            {
                p=sam[p].ch[str[j]-'a'];
            }
            if(p)
            {
                LCT::makeroot(1);
                LCT::access(p);
                LCT::splay(p);
                printf("%lld\n",LCT::tag2[p]+LCT::tag[LCT::tree[p][1]]+LCT::v[p]);
            }
            else
            {
                puts("0");
            }
        }
    }
    return 0;
}

DQS的trie