ACM-ICPC 2018 南京赛区网络预赛 An Easy Problem On The Trees [LCT]

    #include<stdio.h>
    #include<algorithm>
    #define N 100005
    #define MOD 998244353
    using namespace std;
    typedef long long ll;
    //struct stp{ll x,y,a,b;}a[N];
    //bool cmp(stp a,stp b){return a.a<b.a;}
    ll rev[N],ch[N][2],V[N],pre[N],fa[N],st[N],t,sizesum[N],n,sizexu[N],du[N];
    //splay中数组：rev反转标记 ch树的儿子节点
    //V节点value pre节点的父节点 st存节点的栈
    //其他数组：fa
    ll find(ll x){return fa[x]==x?x:fa[x]=find(fa[x]);}//并查集
    bool is_root(ll x){return ch[pre[x]][0]!=x&&ch[pre[x]][1]!=x;}
    //判断x是否为其中一颗splay的根节点
    void reverse(ll x)
    {
    rev[x]^=1;swap(ch[x][0],ch[x][1]);
    rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;
    }
    void update(ll x)
    {
    sizesum[x]=sizexu[x]+sizesum[ch[x][0]]+sizesum[ch[x][1]]+1;
    }
    void rotate(ll x)
    {
    ll y=pre[x],z=pre[y];
    bool f=ch[y][1]==x;
    if(!is_root(y))ch[z][ch[z][1]==y]=x;
    ch[y][f]=ch[x][!f];ch[x][!f]=y;
    pre[x]=z;pre[y]=x;pre[ch[y][f]]=y;
    update(y);update(x);
    }
    void splay(ll x)
    {
    st[t=1]=x;
    for(ll y=x;!is_root(y);st[++t]=y=pre[y]);
    for(;t;t--)if(rev[st[t]])reverse(st[t]);
    for(;!is_root(x);rotate(x))if(!is_root(pre[x]))
        ch[pre[x]][0]==x^ch[pre[pre[x]]][0]==pre[x]?rotate(x):rotate(pre[x]);
    update(x);
    }
    void access(ll x)
    {
    for(ll t=0;x;ch[x][1]=t,t=x,x=pre[x])
    {
        if(t)update(t);
        splay(x);
        sizexu[x]+=sizesum[ch[x][1]]-sizesum[t];
    }
    }
    void make_root(ll x){access(x);splay(x);rev[x]^=1;}
    void link(ll x,ll y){make_root(x);make_root(y);pre[x]=y;du[x]++,du[y]++;sizexu[y]+=sizesum[x];}//将x的父亲设为y
    void cut(ll x,ll y){make_root(x);access(y);splay(y);pre[x]=ch[y][0]=0;sizesum[y]-=sizesum[x];du[x]--;du[y]--;}
    
    bool is_link(ll x,ll y){
    make_root(x);
    access(y);
    splay(x);
    ll u=y;
    while(pre[u])u=pre[u];
    return u==x;
    }
    ll inv[N];
    int main()
    {
    ll m;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)sizesum[i]=1;
    for(ll i=1;i<n;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        link(u,v);
    }
    inv[1]=1;
    for(ll i=2;i<=n;i++)inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    while(m--){
        ll op,x,y;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld",&x,&y);
            if(!is_link(x,y))
                link(x,y);
            else printf("-1\n");
        }
        else if(op==2){
            scanf("%lld%lld",&x,&y);
            if(is_link(x,y)&&x!=y){
                splay(y);
                if(rev[y])reverse(y);
                ll fa=ch[y][0];
                if(rev[fa])reverse(fa);
                while(ch[fa][1])
                {
                    fa=ch[fa][1];
                    if(rev[fa])reverse(fa);
                }
                cut(y,fa);
            }
            else printf("-1\n");
        }
        else {
            scanf("%lld",&x);
            make_root(x);
            ll ans=inv[du[x]]*(sizesum[x]-1)*2%MOD;
            printf("%lld\n",ans);
        }
    }
    return 0;
    }