LCT萌新求助

回复帖子

@_tourist_  2020-08-04 10:42 回复
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200200;
const int MOD=51061;
int ADD(int x,int y){x+=y; return x>=MOD ? x-MOD : x;}
int MUL(int x,int y){return 1ll*x*y%MOD;}
int n,val[N],Q;

#define ls ch[x][0]
#define rs ch[x][1]
namespace LCT{
    int ch[N][2],fa[N],sz[N],val[N],sum[N],rev[N],add[N],mul[N];
    void init(int x){sum[x]=1,val[x]=1,rev[x]=add[x]=0,mul[x]=1,sz[x]=1; ch[x][0]=ch[x][1]=0;}
    int getdir(int x){return (ch[fa[x]][1]==x);}//0:left 1:right
    int isRoot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
    void pushup(int x){
        sum[x]=ADD(ADD(sum[ls],sum[rs]),val[x]);
        sz[x]=sz[ls]+sz[rs]+1;
    }
    void pushdown(int x){
        if(mul[x]!=1)
        {
            if(ls) mul[ls]=MUL(mul[ls],mul[x]), add[ls]=MUL(add[ls],mul[x]), sum[ls]=MUL(sum[ls],mul[x]), val[ls]=MUL(val[ls],mul[x]);
            if(rs) mul[rs]=MUL(mul[rs],mul[x]), add[rs]=MUL(add[rs],mul[x]), sum[rs]=MUL(sum[rs],mul[x]), val[rs]=MUL(val[rs],mul[x]);
            mul[x]=1;
        }
        if(add[x])
        {
            if(ls) add[ls]=ADD(add[x],add[ls]), sum[ls]=ADD(sum[ls],MUL(sz[ls],add[x])), val[ls]=ADD(val[ls],add[x]);
            if(rs) add[rs]=ADD(add[x],add[rs]), sum[rs]=ADD(sum[rs],MUL(sz[rs],add[x])); val[rs]=ADD(val[rs],add[x]);
            add[x]=0;
        }
        if(rev[x])
        {

            if(ls) swap(ch[ls][0],ch[ls][1]), rev[ls]^=1;
            if(rs) swap(ch[rs][0],ch[rs][1]), rev[rs]^=1;
            rev[x]=0;
        }
    }
    void pushall(int x){if(!isRoot(x)) pushall(fa[x]); pushdown(x);}
    void rotate(int x){
        int y=fa[x],z=fa[y],dirx=getdir(x),diry=getdir(y);
        if(!isRoot(y)) ch[z][diry]=x;
        ch[y][dirx]=ch[x][dirx^1]; if(ch[x][dirx^1]) fa[ch[x][dirx^1]]=y;
        ch[x][dirx^1]=y; fa[y]=x; fa[x]=z;
        pushup(y); pushup(x);
    }
    void splay(int x){
        pushall(x);
        int F=fa[x];
        while(!isRoot(x))
        {
            if(!isRoot(F))
            {
                if(getdir(F)==getdir(x)) rotate(F);
                else rotate(x);
            }
            rotate(x);
            F=fa[x];
        }
    }
    void access(int x){
        for(int now=0;x!=0;now=x,x=fa[x])
        { 
            splay(x); 
            ch[x][1]=now; pushup(x);
        }
    }
    void makeroot(int x){
        access(x); 
        splay(x);
        rev[x]^=1; swap(ls,rs);
    }
    int findroot(int x){
        access(x); splay(x);
        while(ch[x][0]) 
        {
            pushdown(x);
            x=ch[x][0];
        }
        splay(x);
        return x;
    }
    void link(int x,int y){
        makeroot(x);
        fa[x]=y; 
        //pushup(y)????
    }
    void cut(int x,int y){
        makeroot(x); 
        access(y); splay(y);
        fa[x]=0; ch[y][0]=0;
        pushup(y);
    }
    void split(int x,int y){
        makeroot(x);
        access(y); splay(y);
    }//y is the root

    void update_add(int x,int y,int v){
        split(x,y);
        val[y]=ADD(val[y],v); add[y]=ADD(add[y],v);
        sum[x]=ADD(sum[x],MUL(v,sz[x]));
    }
    void update_mul(int x,int y,int v){
        split(x,y);
        val[y]=MUL(val[y],v); add[y]=MUL(add[y],v);
        mul[y]=MUL(mul[y],v); sum[y]=MUL(sum[y],v);
    }
    int query(int x,int y){
        split(x,y);
        return sum[y];
    }
}

int vis[N];
int main()
{
    memset(vis,0,sizeof(vis));
    scanf("%d%d",&n,&Q);
    for(int i=1;i<n;i++) 
    {
        int x,y; scanf("%d%d",&x,&y);
        if(!vis[x]) LCT::init(x);
        if(!vis[y]) LCT::init(y);
        vis[x]=1; vis[y]=1;
        LCT::link(x,y);
    }
    while(Q--)
    {
        char opt[2]; scanf("%s",opt); getchar();
        if(opt[0]=='+'){
            int u,v,c; scanf("%d%d%d",&u,&v,&c);
            LCT::update_add(u,v,c);
        } else if(opt[0]=='-'){
            int u1,v1,u2,v2; scanf("%d%d%d%d",&u1,&v1,&u2,&v2);
            LCT::cut(u1,v1); 
            LCT::link(u2,v2);
        } else if(opt[0]=='*'){
            int u,v,c; scanf("%d%d%d",&u,&v,&c);
            LCT::update_mul(u,v,c);
        } else{
            int u,v; scanf("%d%d",&u,&v);
            printf("%d\n",LCT::query(u,v));
        }
    }
    return 0;
}

在90行 $link$函数里如果最后加上 $pushup(y)$就会WA,请问大佬们为什么呀QAQ

@JK_LOVER 2020-08-04 10:46 回复 举报
void link(int x,int y){
        makeroot(x);
        fa[x]=y; 
        //pushup(y)????
    }

先说这行代码本来就是多余的,link没有改变y的实儿子。

@JK_LOVER 2020-08-04 10:47 回复 举报

再说,y的父亲(祖先)被修改过。标记要下传。

    void link(int x,int y){
        makeroot(x);
        access(y);
        splay(y);
        fa[x]=y; 
        pushup(y);
    }
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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