bzoj 2631: tree LCT

→←

新博客链接：

【想说的话】

数据结构调起来可真是令人身心偷税啊

【题解】

pushdown好好搞搞...

还有不能用long long....会TLE，得用unsigned int...

【代码】

#include<bits/stdc++.h>

#define MAXN 100010
#define mod 51061
#define ls son[x][0]
#define rs son[x][1]

typedef unsigned int ll;

using namespace std;

inline ll rd(){
	ll x=0,y=1;char c=getchar();
	while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*y;
}

int n,m;
int son[MAXN][2],fa[MAXN],stk[MAXN];
ll sum[MAXN],val[MAXN],add[MAXN],mul[MAXN],sz[MAXN];
bool rev[MAXN];

inline bool isroot(int x){
	return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}

inline bool is_right(int x){
	return son[fa[x]][1]==x;
}

inline void pushup(int x){
	sz[x]=sz[ls]+sz[rs]+1;
	sum[x]=(sum[ls]+sum[rs]+val[x])%mod;
}

inline void pushdown(int x){
	if(mul[x]!=1){
		val[ls]=val[ls]*mul[x]%mod;
		val[rs]=val[rs]*mul[x]%mod;
		mul[ls]=mul[ls]*mul[x]%mod;
		mul[rs]=mul[rs]*mul[x]%mod;
		add[ls]=add[ls]*mul[x]%mod;
		add[rs]=add[rs]*mul[x]%mod;
		sum[ls]=sum[ls]*mul[x]%mod;
		sum[rs]=sum[rs]*mul[x]%mod;
		mul[x]=1;
	}
	if(add[x]){
		sum[ls]=(sum[ls]+add[x]*sz[ls])%mod;
		sum[rs]=(sum[rs]+add[x]*sz[rs])%mod;
		add[ls]=(add[ls]+add[x])%mod;
		add[rs]=(add[rs]+add[x])%mod;
		val[ls]=(val[ls]+add[x])%mod;
		val[rs]=(val[rs]+add[x])%mod;
		add[x]=0;
	}
	if(rev[x]){
		rev[x]^=1,rev[ls]^=1,rev[rs]^=1;
		swap(ls,rs);
	}
}

inline void Rotate(int x){
	int f=fa[x],ff=fa[f],which=is_right(x);
	if(!isroot(f))son[ff][son[ff][1]==f]=x;
	son[f][which]=son[x][which^1];
	fa[son[f][which]]=f;fa[f]=x;
	son[x][which^1]=f;fa[x]=ff;
	pushup(f);pushup(x);
}

void getdown(int x){
	if(!isroot(x))getdown(fa[x]);
	pushdown(x);
}

inline void splay(int x){
	getdown(x);
	while(!isroot(x)){
		int f=fa[x];
		if(!isroot(f))Rotate((is_right(x)==is_right(f)?f:x));
		Rotate(x);
	}
}

inline void access(int x){
	int t=0;
	while(x){
		splay(x);
		rs=t;
		pushup(x);
		t=x;x=fa[x];
	}
}

inline void toroot(int x){
	access(x);splay(x);
	rev[x]^=1;
}

inline void link(int x,int y){
	toroot(x);
	fa[x]=y;
	splay(x);
}

inline void cut(int x,int y){
	toroot(x);access(y);splay(y);
	son[y][0]=fa[x]=0;
}

inline int Find(int x){
	access(x);splay(x);
	while(ls)x=ls;
	return x;
}

inline void split(int x,int y){
	toroot(x);access(y);splay(y);
}

inline void modify_add(int x,int y,ll k){
	split(x,y);
	sum[y]=(sum[y]+sz[y]*k)%mod;
	add[y]=(add[y]+k)%mod;
	val[y]=(val[y]+k)%mod;
}

inline void modify_mul(int x,int y,ll k){
	split(x,y);
	sum[y]=sum[y]*k%mod;
	add[y]=add[y]*k%mod;
	mul[y]=mul[y]*k%mod;
	val[y]=val[y]*k%mod;
}

int main(){
	n=rd(),m=rd();
	for(int i=1; i<=n; i++)sz[i]=val[i]=sum[i]=mul[i]=1;
	for(int i=1; i<n; i++){
		int x=rd(),y=rd();
		link(x,y);
	}
	char op[2];
	int u,v;
	while(m--){
		scanf("%s",op);
		u=rd(),v=rd();
		if(op[0]=='+'){
			ll x=rd();
			modify_add(u,v,x);
		}
		if(op[0]=='-'){
			int x=rd(),y=rd();
			cut(u,v);link(x,y);
		}
		if(op[0]=='*'){
			ll x=rd();
			modify_mul(u,v,x);
		}
		if(op[0]=='/'){
			split(u,v);
			printf("%u",sum[v]);
		}
	}
	
	return 0;
}