[国家集训队] Tree II 题解报告

[国家集训队] Tree II

一道·真·板子·题

就是练习LCT懒标记的题目

除了翻转标记以外还要维护乘法标记和加法标记

注意加法标记和乘法标记的维护！！！

加法标记

因为splay的区间大小不是固定的，所以我们要维护size，并且子树的sum要加上size乘上标记

其他的就只用直接加上即可

void pushadd(ll x,ll c){
	t[x].sum=(t[x].sum+t[x].sz*c%P)%P;
	t[x].val=(t[x].val+c)%P;
	t[x].add=(t[x].add+c)%P;
}

乘法标记

由于乘法的优先级要大于加法

所以我们的加法标记也要乘上乘法标记值

void pushmul(ll x,ll c){
	t[x].sum=t[x].sum*c%P;
	t[x].val=t[x].val*c%P;
	t[x].mul=t[x].mul*c%P;
	t[x].add=t[x].add*c%P;
}

注意：int过不了！！！

CODE

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
const ll N=1e5+2,P=51061;
ll n,q,s[N];
struct node{ll ch[2],p,sum,tag,sz,val,mul,add;}t[N];
void pushtag(ll x){
	swap(t[x].ch[0],t[x].ch[1]);
	t[x].tag^=1;
}
void pushmul(ll x,ll c){
	t[x].sum=t[x].sum*c%P;
	t[x].val=t[x].val*c%P;
	t[x].mul=t[x].mul*c%P;
	t[x].add=t[x].add*c%P;
}
void pushadd(ll x,ll c){
	t[x].sum=(t[x].sum+t[x].sz*c%P)%P;
	t[x].val=(t[x].val+c)%P;
	t[x].add=(t[x].add+c)%P;
}
void pushup(ll x){
	t[x].sum=(t[t[x].ch[0]].sum+t[x].val+t[t[x].ch[1]].sum)%P;
	t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+1;
}

void pushdown(ll x){
	if(t[x].mul!=1){
		pushmul(t[x].ch[0],t[x].mul);
		pushmul(t[x].ch[1],t[x].mul);
		t[x].mul=1;
	}
	if(t[x].add){
		pushadd(t[x].ch[0],t[x].add);
		pushadd(t[x].ch[1],t[x].add);
		t[x].add=0;
	}
	if(t[x].tag){
		pushtag(t[x].ch[0]);
		pushtag(t[x].ch[1]);
		t[x].tag=0;
 	}
}
bool isrt(ll x){//判断节点x是否是当前实树的根
	return t[t[x].p].ch[0]!=x&&t[t[x].p].ch[1]!=x;
}
void rotate(ll x){//x上旋 
	ll y=t[x].p,z=t[y].p;
	ll k=(t[y].ch[1]==x);//x原来的位置 
	if(!isrt(y)) t[z].ch[(t[z].ch[1]==y)]=x;//x代替y位置 
	t[x].p=z;
	t[y].ch[k]=t[x].ch[k^1];
	t[t[x].ch[k^1]].p=y;
	t[x].ch[k^1]=y;
	t[y].p=x;
	pushup(y);
	pushup(x);
}
void splay(ll x){//x上旋到根 
	ll top=0,r=x;
	s[++top]=r;
	while(!isrt(r)){
		s[++top]=r=t[r].p;
	}
	while(top) pushdown(s[top--]);
	while(!isrt(x)){
		ll y=t[x].p,z=t[y].p;
		if(!isrt(y)){//y不为目标位置 
			if((t[y].ch[1]==x)^(t[z].ch[1]==y)) rotate(x);//不在同一直线上 
			else rotate(y);//在同一直线上 
		}
		rotate(x);
 	}
}
void access(ll x){// 把根节点到x的路径上的边全部变为实边，同时将x变成splay的根节点
	ll z=x;
	for(ll y=0;x;y=x,x=t[x].p){
		splay(x);
		t[x].ch[1]=y;//右子树 
		pushup(x);
	}
	splay(z);
}
void makert(ll x){// 将x变成原树的根节点
	access(x);//打通一条从根到x的路径 然后将x旋到根 
	//首先 打通一条从根到x的路径 后 x 是 d最大的点 
	//因此 此时，x必然是Splay中中序遍历最后得到的点 
	pushtag(x);//翻转Splay ， x成为 中序遍历 第一个点->即原树根节点 
}
ll findrt(ll x) {// 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
	access(x);//x与原树根在同一splay内
	//由于每个Splay中维护的节点按中序遍历得到的顺序在原树中深度依次增加1
    //所以根节点必然是Splay中序遍历顺序为1的节点
	while(t[x].ch[0]){
		pushdown(x);
		x=t[x].ch[0];
	}
	//路径深度最小 
	splay(x);
	return x;
}
void split(ll x,ll y){ // 给x和y之间的路径建1个splay，其根节点是y
	makert(x);
	access(y);
}
void link(ll x,ll y){//如果x和y不连通,加1条x和y之间的边
	makert(x);// 将x作为它所在树的根
	if(findrt(y)!=x){//不连通 
		t[x].p=y;//更新x的父亲为y
	}
}
bool back(ll x,ll y){//y是否是x的后继 
	return t[x].ch[1]==y&&!t[y].ch[0];
}
void cut(ll x,ll y){// 如果x和y之间存在边，则删除该边
	split(x,y);//只剩下x->y,x是y的做儿子 
	if(t[x].ch[1]||t[x].p!=y||t[y].ch[1])return ;
	t[t[y].ch[0]].p=0;
	t[y].ch[0]=0;
}
int main(){
	scanf("%lld%lld",&n,&q);
	for(ll i=1;i<=n;i++){
		t[i].val=t[i].sz=t[i].mul=1;
	}
	for(ll i=1,x,y;i<n;i++){
		scanf("%lld%lld",&x,&y);
		link(x,y);
	}
	for(ll i=1;i<=q;i++){
		char op[10];
		ll x,y,k;
		scanf("%s",op);
		if(op[0]=='+'){
			scanf("%lld%lld%lld",&x,&y,&k);
			split(x,y),pushadd(y,k);
		}else if(op[0]=='-'){
			scanf("%lld%lld",&x,&y);
			cut(x,y);
			scanf("%lld%lld",&x,&y);
			link(x,y);
		}else if(op[0]=='*'){
			scanf("%lld%lld%lld",&x,&y,&k);
			split(x,y),pushmul(y,k);
		}else{
			scanf("%lld%lld",&x,&y);
			split(x,y);
			printf("%lld\n",t[y].sum);
		}
	}
	return 0;
}