为什么删边和加边的过程不用像P4219改变siz大小

回复帖子

@奇米 2020-05-01 20:24 回复 举报

而那道题目还要记录:一个点的实际siz,以及虚点的个数

@奇米 2020-05-01 21:06 回复 举报
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int N=1e5+5;
const int mo=51061;

int n,m,stak[N],siz[N],top;

struct Node
{
    int fa,ch[2],val,sum;
    int mul,add,laz;
};
Node t[N];

inline void Add(int &x,int y)
{
    x+=y;
    if(x>=mo) x%=mo;
}

struct LCT
{
    inline void pushup(int x)
    {
        int ls=t[x].ch[0];
        int rs=t[x].ch[1];
        siz[x]=siz[ls]+siz[rs]+1;
        t[x].sum=(t[ls].sum+t[rs].sum+t[x].val)%mo;
    }
    inline void pushadd(int x,int val)
    {
        Add(t[x].sum,siz[x]*val);
        Add(t[x].val,val);
        Add(t[x].add,val);
    }
    inline void pushmul(int x,int val)
    {
        t[x].sum=(t[x].sum*val)%mo;
        t[x].val=(t[x].val*val)%mo;
        t[x].mul=(t[x].mul*val)%mo;
        t[x].add=(t[x].add*val)%mo;
    }
    inline void pushdown(int x)
    {
        if(t[x].add) 
        {
            int ls=t[x].ch[0];
            int rs=t[x].ch[1];
            pushadd(ls,t[x].add);
            pushadd(rs,t[x].add);
            t[x].add=0;
        }
        if(t[x].mul!=1ll)
        {
            int ls=t[x].ch[0];
            int rs=t[x].ch[1];
            pushmul(ls,t[x].mul);
            pushmul(rs,t[x].mul);
            t[x].mul=1;
        }
        if(t[x].laz)
        {
            swap(t[x].ch[0],t[x].ch[1]);
            t[t[x].ch[0]].laz^=1;
            t[t[x].ch[1]].laz^=1;
            t[x].laz=0;
        }
    }
    inline bool pd(int x)
    {
        return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;
    }
    inline void rotate(int x)
    {
        int y=t[x].fa;
        int z=t[y].fa;
        int k=t[y].ch[1]==x;
        if(!pd(y)) t[z].ch[y==t[z].ch[1]]=x;
        t[x].fa=z;
        t[y].ch[k]=t[x].ch[k^1];
        t[t[x].ch[k^1]].fa=y;
        t[x].ch[k^1]=y;
        t[y].fa=x;
        pushup(y);
        pushup(x);
    }
    inline void splay(int x)
    {
        stak[top=1]=x;
        for ( int i=x;!pd(i);i=t[i].fa ) stak[++top]=t[i].fa;
        for ( int i=top;i;i--) pushdown(stak[i]);
        while(!pd(x))
        {
            int y=t[x].fa,z=t[y].fa;
            if(!pd(y))
                (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x)
    {
        for ( int y=0;x;y=x,x=t[x].fa )
            splay(x),t[x].ch[1]=y,pushup(x);
    }
    inline void makert(int x)
    {
        access(x);
        splay(x);
        t[x].laz^=1;
    }
    inline int findrt(int x)
    {
        access(x);
        splay(x);
        while(t[x].ch[0]) pushdown(x),x=t[x].ch[0];
        splay(x);
        return x;
    }
    inline void split(int x,int y)
    {
        makert(x);
        access(y);
        splay(y);
    }
    inline void cut(int x,int y)
    {
        makert(x);
        if(findrt(y)==x&&t[y].fa==x&&!t[y].ch[0])
        {
            t[y].fa=0;
            t[x].ch[1]=0;
            pushup(x);
        }
    }
    inline void link(int x,int y)
    {
        makert(x);
        makert(y);
        if(findrt(x)==findrt(y)) return;
        t[x].fa=y;
        pushup(y);
    }
};
LCT T;

signed main()
{
    freopen("a.in","r",stdin); 
    n=read();
    m=read();
    for ( int i=1;i<=n;i++ ) 
        t[i].val=t[i].mul=siz[i]=1;
    for ( int i=1;i<n;i++ ) 
    {
        int x,y;
        x=read(),y=read();
        T.link(x,y);
    }
    for (;m--;)
    {
        char op[3];
        int x,y;
        scanf("%s",op+1);
        x=read(),y=read();
        if(op[1]=='+')
        {
            T.split(x,y);
            int v=read();
            T.pushadd(y,v);
        }
        if(op[1]=='-') 
        {
            int xx=read(),yy=read();
            T.cut(x,y);
            T.link(xx,yy);
        }
        if(op[1]=='*')
        {
            int val=read();
            T.split(x,y);
            T.pushmul(y,val);
        }
        if(op[1]=='/')
        {
            T.split(x,y);
            printf("%lld\n",t[y].sum);
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。