萌新刚学OI 1e-18ms,求助

回复帖子

@suyiheng 2019-08-14 11:05 回复
#include<iostream>
#include<cstdio>
using namespace std;
struct data{
    long long fa,ch[2],s,v,add,ins,siz;
    bool la;
}t[1000001];
long long n,m,x,y,x1,y1,s[1000001],val;
char id[11];
bool check(long long a){
    return t[t[a].fa].ch[0]==a||t[t[a].fa].ch[1]==a;
}
void up(long long a){
    t[a].s=(t[t[a].ch[0]].s+t[t[a].ch[1]].s+t[a].v)%51061;
    t[a].siz=t[t[a].ch[0]].siz+t[t[a].ch[1]].siz+1;
}
void down(long long a){
    if(t[a].add!=1){
        if(t[a].ch[0]){
            t[t[a].ch[0]].add=(t[t[a].ch[0]].add*t[a].add)%51061;
            t[t[a].ch[0]].v=(t[t[a].ch[0]].v*t[a].add)%51061;
            t[t[a].ch[0]].s=(t[t[a].ch[0]].s*t[a].add)%51061;
            t[t[a].ch[0]].ins=(t[t[a].ch[0]].ins*t[a].add)%51061;
        }
        if(t[a].ch[1]){
            t[t[a].ch[1]].add=(t[t[a].ch[1]].add*t[a].add)%51061;
            t[t[a].ch[1]].v=(t[t[a].ch[1]].v*t[a].add)%51061;
            t[t[a].ch[1]].s=(t[t[a].ch[1]].s*t[a].add)%51061;
            t[t[a].ch[1]].ins=(t[t[a].ch[1]].ins*t[a].add)%51061;
        }
    }
    if(t[a].ins!=0){
        if(t[a].ch[0]){
            t[t[a].ch[0]].v=(t[t[a].ch[0]].v+t[a].ins)%51061;
            t[t[a].ch[0]].s=(t[t[a].ch[0]].s+t[a].ins*t[t[a].ch[0]].siz)%51061;
            t[t[a].ch[0]].ins=(t[t[a].ch[0]].ins+t[a].ins)%51061;
        }
        if(t[a].ch[1]){
            t[t[a].ch[1]].v=(t[t[a].ch[1]].v+t[a].ins)%51061;
            t[t[a].ch[1]].s=(t[t[a].ch[1]].s+t[a].ins*t[t[a].ch[1]].siz)%51061;
            t[t[a].ch[1]].ins=(t[t[a].ch[1]].ins+t[a].ins)%51061;
        }
    }
    t[a].add=1;
    t[a].ins=0;
    if(t[a].la){
        if(t[a].ch[0]){
            t[t[a].ch[0]].la^=1;
            swap(t[t[a].ch[0]].ch[0],t[t[a].ch[0]].ch[1]);
        }
        if(t[a].ch[1]){
            t[t[a].ch[1]].la^=1;
            swap(t[t[a].ch[1]].ch[0],t[t[a].ch[1]].ch[1]);
        }
        t[a].la=0;
    }
}
void turn(long long a){
    long long b=t[a].fa;
    long long c=t[b].fa,k=(t[b].ch[1]==a);
    long long w=t[a].ch[!k];
    if(check(b))t[c].ch[t[c].ch[1]==b]=a;
    t[a].ch[!k]=b;
    t[b].ch[k]=w;
    if(w)t[w].fa=b;
    t[b].fa=a;
    t[a].fa=c;
    up(b);
}
void splay(long long a){
    long long b=a,c=0;
    c++;
    s[c]=b;
    while(check(b)){
        c++;
        b=t[b].fa;
        s[c]=b;
    }
    while(c){
        down(s[c]);
        c--;
    }
    while(check(a)){
        b=t[a].fa;
        c=t[b].fa;
        if(check(b)){
            if((t[b].ch[0]==a&&t[c].ch[0]==b)||(t[b].ch[1]==a&&t[c].ch[1]==b))turn(b);
            else turn(a);
        }
        turn(a);
    }
    up(a);
}
void access(long long a){
    for(long long i=0;a;){
        splay(a);
        t[a].ch[1]=i;
        up(a);
        i=a;
        a=t[a].fa;
    }
}
void makeroot(long long a){
    access(a);
    splay(a);
    swap(t[a].ch[0],t[a].ch[1]);
    t[a].la^=1;
}
long long findroot(long long a){
    access(a);
    splay(a);
    while(t[a].ch[0]){
        down(a);
        a=t[a].ch[0];
    }
    splay(a);
    return a;
}
void split(long long a,long long b){
    makeroot(a);
    access(b);
    splay(b);
}
void link(long long a,long long b){
    makeroot(a);
    t[a].fa=b;
}
void cut(long long a,long long b){
    makeroot(a);
    t[b].fa=0;
    t[a].ch[1]=0;
    up(a);
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;i++){
        t[i].v=1;
        t[i].s=1;
        t[i].siz=1;
        t[i].add=0;
    }
    for(long long i=1;i<n;i++){
        scanf("%lld%lld",&x,&y);
        link(x,y);
    }
    for(long long i=1;i<=m;i++){
        scanf("%s%lld%lld",id+1,&x,&y);
        if(id[1]=='/'){
            split(x,y);
            printf("%lld\n",t[y].s);
        }else if(id[1]=='+'){
            scanf("%lld",&val);
            split(x,y);
            t[y].ins=(t[y].ins+val)%51061;
            t[y].v=(t[y].v+val)%51061;
            t[y].s=(t[y].s+val*t[y].siz)%51061;
        }else if(id[1]=='-'){
            scanf("%lld%lld",&x1,&y1);
            cut(x,y);
            link(x1,y1);
        }else{
            scanf("%lld",&val);
            split(x,y);
            t[y].add=(val*t[y].add+t[y].ins*val)%51061;
            t[y].s=(t[y].ins*val+t[y].s*val)%51061;
            t[y].v=(t[y].ins*val+t[y].v*val)%51061;
            t[y].ins=0;
        }
    }
}

可能我LCT板子咕了

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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