BZOJ 2631 tree LCT

发布时间:2017-7-1 11:49:42编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"BZOJ 2631 tree LCT ",主要涉及到BZOJ 2631 tree LCT 方面的内容,对于BZOJ 2631 tree LCT 感兴趣的同学可以参考一下。

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 100010#define mod 51061using namespace std;typedef unsigned int uint;char s[5];uint x,y;uint n,q;uint rt[N];uint rev[N];uint mul[N];uint add[N];uint sum[N];uint val[N]; uint size[N];uint ch[N][2];uint fa[N];void init(){    for(int i=1;i<=n;i++)mul[i]=1,rt[i]=1,size[i]=1,val[i]=1;}void pushdown_add_and_mul_operation(int x,int add_opt,int mul_opt){    sum[x]=(sum[x]*mul_opt+size[x]*add_opt)%mod;    val[x]=(val[x]*mul_opt+add_opt)%mod;    add[x]=(add[x]*mul_opt+add_opt)%mod;    mul[x]=(mul[x]*mul_opt)%mod;} void pushdown(uint x){    if(rev[x])    {        rev[ch[x][0]]^=1,rev[ch[x][1]]^=1;        rev[x]^=1;        swap(ch[x][0],ch[x][1]);    }    if(mul[x]!=1||add[x]!=0)    {        if(ch[x][0]!=0)        {            pushdown_add_and_mul_operation(ch[x][0],add[x],mul[x]);        }        if(ch[x][1]!=0)        {            pushdown_add_and_mul_operation(ch[x][1],add[x],mul[x]);        }        mul[x]=1,add[x]=0;    }}void down(uint x){    if(!rt[x])down(fa[x]);    pushdown(x);}void pushup(uint x){    size[x]=(size[ch[x][0]]+size[ch[x][1]]+1)%mod;    sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+val[x])%mod;}void rotate(uint x){    uint y=fa[x],kind=ch[y][1]==x;    ch[y][kind]=ch[x][!kind];    fa[ch[y][kind]]=y;    ch[x][!kind]=y;    fa[x]=fa[y];    fa[y]=x;    if(rt[y])rt[y]=0,rt[x]=1;    else ch[fa[x]][ch[fa[x]][1]==y]=x;    pushup(y);}void splay(uint x){    down(x);    while(!rt[x])    {        uint y=fa[x],z=fa[y];        if(rt[y])rotate(x);        else if((ch[y][1]==x)==(ch[z][1]==y))        {            rotate(y),rotate(x);        }else rotate(x),rotate(x);    }    pushup(x);}void access(uint x){    uint y=0;    while(x)    {        splay(x);        rt[ch[x][1]]=1,rt[y]=0;        ch[x][1]=y;        pushup(x);        y=x,x=fa[x];    }}void movetoroot(uint x){    access(x);    splay(x);    rev[x]=1;    pushdown(x);}void link(uint x,uint y){    movetoroot(x);    fa[x]=y;}void cut(uint x,uint y){    movetoroot(x);    access(y);    splay(y);    rt[x]=1;    ch[y][0]=0;    fa[x]=0;}int main(){    scanf("%u%u",&n,&q);    init();    for(int i=1;i<n;i++)    {        scanf("%u%u",&x,&y);        link(x,y);    }    for(int i=1;i<=q;i++)    {        scanf("%s",s);        uint x,y,z,w;        switch(s[0])        {            case '+':                scanf("%u%u%u",&x,&y,&z);                movetoroot(y);access(x);splay(x);                pushdown_add_and_mul_operation(x,z,1);                break;            case '-':scanf("%u%u%u%u",&x,&y,&z,&w);cut(x,y);link(z,w);break;            case '*':                 scanf("%u%u%u",&x,&y,&z);                movetoroot(y);access(x);splay(x);                pushdown_add_and_mul_operation(x,0,z);                break;            case '/':                scanf("%u%u",&x,&y);                movetoroot(y);access(x);splay(x);                printf("%u\n",sum[x]);                break;


上一篇:iOS 画圆形头像
下一篇:一个互联网产品的进化周期大概

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款