社区讨论

AC了但有疑问

P1501[国家集训队] Tree II参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mdoijs3o
此快照首次捕获于
2025/07/29 20:28
7 个月前
此快照最后确认于
2025/11/04 03:31
4 个月前
查看原帖
cutcut函数中,为什么是这样???(见109109行)
CPP
#include<bits/stdc++.h>
#define int long long
#define mod 51061
using namespace std;
const int maxn=6e5+5;
int n,m;
int r[maxn];
struct node {
	int fa,ch[2],v,s,add,mul,sz;
} tree[maxn];
int st[maxn];
int read() {
	char c=getchar();
	int ans=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
	return ans;
}
int noroot(int x) {
	return ((tree[tree[x].fa].ch[0]==x)||(tree[tree[x].fa].ch[1]==x));
}
inline void pushup(int x) {
	tree[x].s=(tree[tree[x].ch[0]].s+tree[tree[x].ch[1]].s+tree[x].v)%mod;
	tree[x].sz=tree[tree[x].ch[0]].sz+tree[tree[x].ch[1]].sz+1;
}
inline void pushr(int x) {
	swap(tree[x].ch[0],tree[x].ch[1]),r[x]^=1;
}
void push_mul(int rt,int x) {
	tree[rt].s=(tree[rt].s*x)%mod;
	tree[rt].add=(tree[rt].add*x)%mod;
	tree[rt].mul=(tree[rt].mul*x)%mod;
	tree[rt].v=(tree[rt].v*x)%mod;
}
void push_add(int rt,int x) {
	tree[rt].s=(tree[rt].s+x*tree[rt].sz)%mod;
	tree[rt].add=(tree[rt].add+x)%mod;
	tree[rt].v=(tree[rt].v+x)%mod;
}
inline void pushdown(int x) {
	if(tree[x].mul!=1){
		push_mul(tree[x].ch[0],tree[x].mul);
		push_mul(tree[x].ch[1],tree[x].mul);
		tree[x].mul=1;
	}
	if(tree[x].add) {
		push_add(tree[x].ch[0],tree[x].add);
		push_add(tree[x].ch[1],tree[x].add);
		tree[x].add=0;
	}
	if(r[x]) {
		if(tree[x].ch[0]) {
			pushr(tree[x].ch[0]);
		}
		if(tree[x].ch[1]) {
			pushr(tree[x].ch[1]);
		}
		r[x]=0;
	}
}
inline void rotate(int x) {
	int y=tree[x].fa,z=tree[y].fa,k=tree[y].ch[1]==x,w=tree[x].ch[!k];
  	if(noroot(y)) {
		tree[z].ch[tree[z].ch[1]==y]=x;
	}
	tree[x].ch[!k]=y;
	tree[y].ch[k]=w;
	if(w) {
		tree[w].fa=y;
	}
	tree[y].fa=x;
	tree[x].fa=z;
	pushup(y);
}
inline void splay(int x) {
	int y=x,z=0;
	st[++z]=y;
	while(noroot(y))st[++z]=y=tree[y].fa;
	while(z)pushdown(st[z--]);
	while(noroot(x)) {
		y=tree[x].fa,z=tree[y].fa;
		if(noroot(y))rotate(((tree[y].ch[0]==x)^(tree[z].ch[0]==y))?x:y);
		rotate(x);
	}
	pushup(x);

}
inline void access(int x) {
	for(int y=0; x; x=tree[y=x].fa) {
		splay(x);
		tree[x].ch[1]=y;
		pushup(x);
	}
}
inline void makeroot(int x) {
	access(x),splay(x),pushr(x);
}
inline void split(int x,int y) {
	makeroot(x);
	access(y);
	splay(y);
}
inline void link(int x,int y) {
	makeroot(x);
	tree[x].fa=y;
}
inline void cut(int x,int y) {
	split(x,y);
	tree[x].fa=tree[y].ch[0]=0;
}
signed main() {
	n=read(),m=read();
	for(int i=1; i<=n; i++) {
		tree[i].v=tree[i].sz=tree[i].mul=1;
	}
	for(int i=1; i<n; i++) {
		int u,v;
		u=read();
		v=read();
		link(u,v);
	}
	for(int o=1; o<=m; o++) {
		char op;
		int x,y,k,l,r;
		cin>>op;
		x=read();
		y=read();
		if(op=='+') {
			k=read();
			split(x,y);
			push_add(y,k);
		} else if(op=='-') {
			l=read();
			r=read();
			cut(x,y);
			link(l,r);
		} else if(op=='*') {
			k=read();
			split(x,y);
			push_mul(y,k);
		} else if(op=='/') {
			split(x,y);
			cout<<tree[y].s<<endl;
		}
	}
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...