求调5pts
查看原帖
求调5pts
538683
Enoch006楼主2024/3/31 22:47

实在找不出哪里写错了,感谢各位大佬/kk/kk

#include <bits/stdc++.h>
#define int long long
#define maxm 500005
#define maxn 1005
#define mod 51061
using namespace std;
int n,m,sum;
struct LCT{
	int ch[2];
	int fa,val,sum,lz,mul,add,sz;
}t[maxm];
int Get(int x){return t[t[x].fa].ch[1]==x;}
int Isroot(int x){return !(t[t[x].fa].ch[1]==x||t[t[x].fa].ch[0]==x);}
void Pushup(int x){t[0]=(LCT){0,0,0,0,0,0,0,0,0};t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+1;t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].val;}
void Rotate(int x){
	int y=t[x].fa,z=t[y].fa,k=Get(x),p=t[x].ch[k^1];
	if(!Isroot(y))t[z].ch[Get(y)]=x;
	t[x].fa=z;t[y].fa=x;t[p].fa=y;
	t[x].ch[k^1]=y;t[y].ch[k]=p;
	Pushup(y);Pushup(x);
}
void Pushdown(int x){
	t[t[x].ch[0]].mul*=t[x].mul%mod;
	t[t[x].ch[1]].mul*=t[x].mul%mod;
	t[t[x].ch[0]].val*=t[x].mul%mod;
	t[t[x].ch[1]].val*=t[x].mul%mod;
	t[t[x].ch[0]].sum*=t[x].mul%mod;
	t[t[x].ch[1]].sum*=t[x].mul%mod;	
	t[t[x].ch[0]].add*=t[x].mul%mod;
	t[t[x].ch[1]].add*=t[x].mul%mod;
	t[x].mul=1;
	t[t[x].ch[0]].add=(t[t[x].ch[0]].add+t[x].add)%mod;
	t[t[x].ch[1]].add=(t[t[x].ch[1]].add+t[x].add)%mod;
	t[t[x].ch[0]].sum=(t[t[x].ch[0]].sum+t[x].add*t[t[x].ch[0]].sz)%mod;
	t[t[x].ch[1]].sum=(t[t[x].ch[1]].sum+t[x].add*t[t[x].ch[1]].sz)%mod;
	t[t[x].ch[0]].val=(t[t[x].ch[0]].val+t[x].add)%mod;
	t[t[x].ch[1]].val=(t[t[x].ch[1]].val+t[x].add)%mod;
	t[x].add=0;
	if(!t[x].lz)return;
	t[t[x].ch[0]].lz^=1;
	t[t[x].ch[1]].lz^=1;
	swap(t[x].ch[0],t[x].ch[1]);
	t[x].lz=0;
}
void Push(int x){
	if(!Isroot(x))Push(t[x].fa);
	Pushdown(x);
	//cout<<x<<"\n";
}
void Splay(int x){
	Push(x);
	//cout<<"???\n";
	for(int f=t[x].fa;!Isroot(x);Rotate(x),f=t[x].fa){
		if(!Isroot(f))Rotate(Get(f)==Get(x)?f:x);
		//cout<<x<<" "<<f<<"\n";
	}
}
void Access(int x){
	for(int p=0;x;p=x,x=t[x].fa){
		Splay(x),t[x].ch[1]=p,Pushup(x);
		//cout<<x<<" "<<t[x].fa<<"\n"; 
	}
	//cout<<"access\n";
}
void Makeroot(int x){
	Access(x);
	//cout<<"???\n";
	Splay(x);
	t[x].lz^=1;
}
void Split(int x,int y){
	Makeroot(x);
	Access(y);
	Splay(y);
}
void Link(int x,int y){
	Split(x,y);
	if(!t[x].fa)t[x].fa=y;
}
void Cut(int x,int y){
	Split(x,y);
	if(!t[x].ch[1]&&t[y].ch[0]==x)t[y].ch[0]=t[x].fa=0;
	Pushup(y);
}
signed main(){
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)t[i]=(LCT){0,0,0,1,1,0,1,0,1};
    for(int i=1;i<n;i++){
    	int x,y;
    	cin>>x>>y;
    	Link(x,y);
	}
	//for(int i=1;i<=n;i++)cout<<i<<" "<<t[i].ch[0]<<" "<<t[i].ch[1]<<" sum"<<t[i].sum<<" val"<<t[i].val<<" add"<<t[i].add<<" mul"<<t[i].mul<<"\n";
	while(m--){
		char op;
		int x,y,c,d;
		cin>>op>>x>>y;
		if(op=='+'){
			cin>>c;
			Split(x,y);
			t[y].add=(t[y].add+c)%mod;
			t[y].val=(t[y].val+c)%mod;
			t[y].sum=(t[y].sum+c*t[y].sz)%mod;
		}
		if(op=='-'){
			cin>>c>>d;
			Cut(x,y);
			Link(c,d);
		}
		if(op=='*'){
			cin>>c;
			Split(x,y);
			t[y].mul*=c%mod;
			t[y].sum*=c%mod;
			t[y].val*=c%mod;
			t[y].add*=c%mod;
		}
		if(op=='/'){
			Split(x,y);
			cout<<t[y].sum%mod<<"\n";
		}
		//for(int i=1;i<=n;i++)cout<<i<<" "<<t[i].ch[0]<<" "<<t[i].ch[1]<<" sum"<<t[i].sum<<" val"<<t[i].val<<" add"<<t[i].add<<" mul"<<t[i].mul<<"\n";
	}
    return 0;
}
2024/3/31 22:47
加载中...