社区讨论

萌新刚学OI,此题WA5,求大佬找错QAQ

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

讨论操作

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

当前回复
9 条
当前快照
1 份
快照标识符
@mi6vwgud
此快照首次捕获于
2025/11/20 11:41
4 个月前
此快照最后确认于
2025/11/20 11:41
4 个月前
查看原帖
我大概都几乎快改成flashhu大佬的题解了,但是还是WA5,根本查不出错qwq
代码长这样:
CPP
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100010
#define mod 51061
#define lson ch[x][0]
#define rson ch[x][1]
#define int long long
using namespace std;

int tag1[N],tag2[N],tag3[N],sum[N],sz[N],f[N],ch[N][2],w[N];

int not_root(int now)
{
	int x=f[now];
	return lson==now||rson==now;
}

int push_up(int x)
{
	sum[x]=(sum[lson]+sum[rson]+w[x])%mod;
	sz[x]=sz[lson]+sz[rson]+1;
}

int rev(int x)
{
	swap(lson,rson);
	tag1[x]^=1;
}

int add(int x,int cost)
{
	sum[x]+=cost*sz[x];
	sum[x]%mod;
	w[x]+=cost;
	w[x]%=mod;
	tag2[x]+=cost;
	tag2[x]%mod;
}

int mul(int x,int cost)
{
	sum[x]*=cost;
	sum[x]%=mod;
	w[x]*=cost;
	w[x]%=mod;
	tag3[x]*=cost;
	tag3[x]%mod;
	tag2[x]*=cost;
	tag2[x]%mod;
}

int push_down(int x)
{
	if(tag3[x]!=1)
	{
		mul(lson,tag3[x]);
		mul(rson,tag3[x]);
		tag3[x]=1;
	}
	if(tag2[x])
	{
		add(lson,tag2[x]);
		add(rson,tag2[x]);
		tag2[x]=0;
	}
	if(tag1[x])
	{
		rev(lson);
		rev(rson);
		tag1[x]=0;
	}
}

int rotate(int x)
{
	int y=f[x],z=f[y],kd=ch[y][1]==x,xs=ch[x][!kd];
	if(not_root(y))
	{
		ch[z][ch[z][1]==y]=x;
	}
	ch[x][!kd]=y;
	ch[y][kd]=xs;
	if(xs) f[xs]=y;
	f[y]=x;
	f[x]=z;
	push_up(y);
}

int push_all(int x)
{
	if(not_root(x))
	{
		push_all(f[x]);
	}
	push_down(x);
}

int splay(int x)
{
	int y,z;
	push_all(x);
	while(not_root(x))
	{
		y=f[x],z=f[y];
		if(not_root(y))
		{
			(ch[y][0]==x)^(ch[z][0]==y)?rotate(x):rotate(y);
		}
		rotate(x);
	}
	push_up(x);
}

int access(int x)
{
	for(int y=0; x; y=x,x=f[x])
	{
		splay(x);
		rson=y;
		push_up(x);
	}
}

int make_root(int x)
{
	access(x);
	splay(x);
	rev(x);
}

int split(int x,int y)
{
	make_root(x);
	access(y);
	splay(y);
}

int link(int x,int y)
{
	make_root(x);
	f[x]=y;
}

int cut(int x,int y)
{
	split(x,y);
	f[x]=ch[y][0]=0;
}

char s[3];
int n,m;

signed main()
{
	scanf("%lld %lld",&n,&m);
	for(int i=1; i<=n; i++)
	{
		sum[i]=w[i]=tag3[i]=sz[i]=1;
	}
	for(int i=1; i<n; i++)
	{
		int from,to;
		scanf("%lld %lld",&from,&to);
		link(from,to);
	}
	for(int i=1; i<=m; i++)
	{
		scanf("%s",s);
		if(s[0]=='*')
		{
			int x,y,cost;
			scanf("%lld %lld %lld",&x,&y,&cost);
			split(y,x);
			mul(x,cost);
		}
		if(s[0]=='-')
		{
			int u1,v1,u2,v2;
			scanf("%lld %lld %lld %lld",&u1,&v1,&u2,&v2);
			cut(u1,v1);
			link(u2,v2);
		}
		if(s[0]=='+')
		{
			int x,y,cost;
			scanf("%lld %lld %lld",&x,&y,&cost);
			split(y,x);
			add(x,cost);
		}
		if(s[0]=='/')
		{
			int u,v;
			scanf("%lld %lld",&u,&v);
			split(u,v);
			printf("%lld\n",sum[v]);
		}
	}
}

回复

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

正在加载回复...