社区讨论
萌新刚学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 条回复,欢迎继续交流。
正在加载回复...