| 记录编号 |
217656 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[国家集训队2012]tree(伍一鸣) |
最终得分 |
100 |
| 用户昵称 |
 stdafx.h |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
8.579 s |
| 提交时间 |
2016-01-05 17:37:22 |
内存使用 |
6.39 MiB |
显示代码纯文本
#define MAXN 100010UL
#define MAXC 5UL
#define uint unsigned int
#define Mod 51061UL
#include <stdio.h>
#include <string.h>
#define L(x) ch[x][0]
#define R(x) ch[x][1]
struct Edge{int v,nx;};
Edge edge[MAXN<<1];
uint n,q,ec,val[MAXN],sum[MAXN],fa[MAXN],mark[MAXN],add[MAXN],mul[MAXN],sta[MAXN],ch[MAXN][2],tag[MAXN],size[MAXN],headlist[MAXN];
char op[MAXC];
/*---------------------------------------------
- mark == 0 is nuuint . +
- mark == 1 is add . +
- mark == 2 is mul . +
- mark == 3 is firstly mul & secondly add . +
---------------------------------------------*/
inline uint in(){
uint x=0,c=getchar();
while(c<'0'||c>'9') c=getchar();
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x;
}
inline bool IsRoot(uint x){
return (fa[x]==0)||(L(fa[x])!=x&&R(fa[x])!=x);
}
inline void Add_Edge(uint u,uint v){
edge[++ec].v=v;
edge[ec].nx=headlist[u];
headlist[u]=ec;
return;
}
inline void dfs(uint p,uint k){
fa[p]=k;
val[p]=sum[p]=size[p]=1;
for(uint i=headlist[p];i;i=edge[i].nx){
if(edge[i].v==k) continue;
dfs(edge[i].v,p);
}
return;
}
inline void Update(uint x){
sum[x]=val[x];
size[x]=1;
if(L(x)) size[x]+=size[L(x)],sum[x]+=sum[L(x)];
if(R(x)) size[x]+=size[R(x)],sum[x]+=sum[R(x)];
sum[x]%=Mod;
size[x]%=Mod;
return;
}
inline void GiveMark(uint mark_type,uint x,uint adding,uint muling){
adding%=Mod;
muling%=Mod;
if(mark_type==1){
add[x]+=adding;
val[x]+=adding;
sum[x]+=size[x]*adding;
if(!mark[x]) mark[x]=1;
else if(mark[x]==2) mark[x]=3;
}
else if(mark_type==2){
val[x]*=muling;
sum[x]*=muling;
if(!mark[x]) mark[x]=2,mul[x]=muling;
else if(mark[x]==1) mark[x]=3,mul[x]=muling,add[x]*=muling;
else if(mark[x]==2) mul[x]*=muling;
else if(mark[x]==3) mul[x]*=muling,add[x]*=muling;
}
else if(mark_type==3){
val[x]*=muling;val[x]+=adding;
sum[x]*=muling;sum[x]+=size[x]*adding;
if(!mark[x]) mark[x]=3,mul[x]=muling,add[x]=adding;
else if(mark[x]==1) mark[x]=3,mul[x]=muling,add[x]*=muling,add[x]%=Mod,add[x]+=adding;
else if(mark[x]==2) mark[x]=3,mul[x]*=muling,add[x]+=adding;
else if(mark[x]==3) mul[x]*=muling,add[x]*=muling,add[x]%=Mod,add[x]+=adding;
}
mul[x]%=Mod;add[x]%=Mod;sum[x]%=Mod;val[x]%=Mod;
return;
}
inline void Swap(uint &x,uint &y){
if(x!=y) x^=y,y^=x,x^=y;
return;
}
inline void PushDown(uint x){
if(tag[x]!=0){Swap(L(x),R(x));tag[L(x)]^=1;tag[R(x)]^=1;tag[x]=0;}
if(mark[x]!=0){
if(L(x)) GiveMark(mark[x],L(x),add[x],mul[x]);
if(R(x)) GiveMark(mark[x],R(x),add[x],mul[x]);
mark[x]=0;add[x]=0;mul[x]=0;
}
return;
}
inline void Rotate(uint x,uint d){
uint y=ch[x][d^1];
ch[x][d^1]=ch[y][d];
fa[ch[x][d^1]]=x;ch[y][d]=x;
if(x==L(fa[x])) L(fa[x])=y;
else if(x==R(fa[x])) R(fa[x])=y;
fa[y]=fa[x];fa[x]=y;
Update(x);return;
}
inline void Splay(uint p){
sta[++sta[0]]=p;
for(uint i=p;!IsRoot(i);i=fa[i]) sta[++sta[0]]=fa[i];
while(sta[0]) PushDown(sta[sta[0]--]);
uint x,y;
while(!IsRoot(p)){
x=fa[p];y=fa[x];
if(IsRoot(x)) Rotate(x,L(x)==p);
else{
if((L(x)==p)==(L(y)==x)){Rotate(y,L(y)==x);Rotate(x,L(x)==p);}
else{Rotate(x,L(x)==p);Rotate(y,L(y)==p);}
}
}
Update(p);
return;
}
inline void Access(uint x){
uint t=0;
while(x){
Splay(x);PushDown(x);
R(x)=t;Update(x);
t=x;x=fa[x];
}
return;
}
inline void MakeRoot(uint x){
Access(x);
Splay(x);
tag[x]^=1;
return;
}
inline void Link(uint x,uint y){
MakeRoot(x);fa[x]=y;
return;
}
inline void Cut(uint x,uint y){
MakeRoot(x);
Access(y);Splay(y);
PushDown(y);
if(L(y)==x) L(y)=fa[x]=0;
Update(y);
return;
}
inline void Add(uint x,uint y,uint c){
Access(y);
uint t=0;
while(x){
Splay(x);PushDown(x);
if(!fa[x]){
val[x]+=c;
val[x]%=Mod;
GiveMark(1,R(x),c,0);
GiveMark(1,t,c,0);
Update(x);
return;
}
R(x)=t;Update(x);
t=x;x=fa[x];
}
return;
}
inline void Mul(uint x,uint y,uint c){
Access(y);
uint t=0;
while(x){
Splay(x);PushDown(x);
if(!fa[x]){
val[x]*=c;
val[x]%=Mod;
GiveMark(2,R(x),0,c);
GiveMark(2,t,0,c);
Update(x);
return;
}
R(x)=t;Update(x);
t=x;x=fa[x];
}
return;
}
inline uint GetAns(uint x,uint y){
Access(y);
uint t=0;
while(x){
Splay(x);PushDown(x);
if(!fa[x]) return (val[x]+sum[R(x)]+sum[t])%Mod;
R(x)=t;Update(x);
t=x;x=fa[x];
}
return 0;
}
int main(){
freopen("nt2012_wym_tree.in","r",stdin);
freopen("nt2012_wym_tree.out","w",stdout);
n=in();q=in();
for(uint i=1,a,b;i<n;i++){
a=in();b=in();
Add_Edge(a,b);
Add_Edge(b,a);
}
dfs(1,0);
for(uint i=0,a,b,c,d;i<q;i++){
scanf("%s",op);
if(op[0]=='+') a=in(),b=in(),c=in(),Add(a,b,c);
else if(op[0]=='-') a=in(),b=in(),c=in(),d=in(),Cut(a,b),Link(c,d);
else if(op[0]=='*') a=in(),b=in(),c=in(),Mul(a,b,c);
else a=in(),b=in(),printf("%u\n",GetAns(a,b));
}
return 0;
}