Lvat_s Blog

又做了一道叫"tree"的题目。。

这题要开unsigned int!!!!

开int会WA!开int会WA!开int会WA!重要的事说三遍

#include<cstdio>
#include<algorithm>
using namespace std;

unsigned int n,q;

struct Node{
unsigned int v,sum,add,rev,mul,siz;
Node *ch[2],*fa;
Node(unsigned int val,Node *fat);
void Pushdown();
void Pushup();
}*root[100005],*Null;

Node::Node(unsigned int val,Node *fat){
v=sum=val;
mul=siz=1;
add=rev=0;
ch[0]=ch[1]=Null;
fa=fat;
}

void Node::Pushdown(){
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
}
if(mul!=1){
	if(ch[0]!=Null){
		ch[0]->mul=(ch[0]->mul*mul)%51061;
		ch[0]->add=(ch[0]->add*mul)%51061;
		ch[0]->sum=(ch[0]->sum*mul)%51061;
		ch[0]->v=(ch[0]->v*mul)%51061;
	}
	if(ch[1]!=Null){
		ch[1]->mul=(ch[1]->mul*mul)%51061;
		ch[1]->add=(ch[1]->add*mul)%51061;
		ch[1]->sum=(ch[1]->sum*mul)%51061;
		ch[1]->v=(ch[1]->v*mul)%51061;
	}
	mul=1;
}
if(add){
	if(ch[0]!=Null){
		ch[0]->add=(ch[0]->add+add)%51061;
		ch[0]->sum=(ch[0]->sum+ch[0]->siz%51061*add)%51061;
		ch[0]->v=(ch[0]->v+add)%51061;
	}
	if(ch[1]!=Null){
		ch[1]->add=(ch[1]->add+add)%51061;
		ch[1]->sum=(ch[1]->sum+ch[1]->siz%51061*add)%51061;
		ch[1]->v=(ch[1]->v+add)%51061;
	}
	add=0;
}
}

void Node::Pushup(){
siz=1;
sum=v;
if(ch[0]!=Null){siz+=ch[0]->siz;sum=(sum+ch[0]->sum)%51061;}
if(ch[1]!=Null){siz+=ch[1]->siz;sum=(sum+ch[1]->sum)%51061;}
}

int Notroot(Node *p){
return (p->fa->ch[0]==p)||(p->fa->ch[1]==p);
}

void Prepare(Node *p){
if(Notroot(p))Prepare(p->fa);
p->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
swap(x->ch[0],x->ch[1]);
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){x->fa=Null;y->ch[0]=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

Node *ToLct(int x){
return root[x];
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->siz=0;
return p;
}

void Add(int x,int y,int z){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
q->add=(q->add+z)%51061;
q->v=(q->v+z)%51061;
q->Pushup();
}

void Mul(int x,int y,int z){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
q->mul=(q->mul*z)%51061;
q->v=(q->v*z)%51061;
q->Pushup();
}

unsigned int Div(int x,int y){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
return q->sum;
}

int main(){
freopen("2631.in","r",stdin);
freopen("2631.out","w",stdout);
scanf("%d %d",&n,&q);
Null=GetNull();
for(int i=1;i<=n;i++)root[i]=new Node(1,Null);
for(int i=1;i<n;i++){
	int u,v;
    scanf("%d %d",&u,&v);
    Link(ToLct(u),ToLct(v));
}
for(int i=1;i<=q;i++){
    char s[3];
    scanf("%s",s);
    if(s[0]=='+'){
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		Add(u,v,c);
    }
    if(s[0]=='-'){
		int u1,v1,u2,v2;
		scanf("%d %d %d %d",&u1,&v1,&u2,&v2);
        Cut(ToLct(u1),ToLct(v1));
        Link(ToLct(u2),ToLct(v2));
    }
    if(s[0]=='*'){
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		Mul(u,v,c);
    }
    if(s[0]=='/'){
		int u,v;
		scanf("%d %d",&u,&v);
		printf("%d\n",Div(u,v));
    }
}
return 0;
}