社区讨论
AC了但有疑问
P1501[国家集训队] Tree II参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mdoijs3o
- 此快照首次捕获于
- 2025/07/29 20:28 7 个月前
- 此快照最后确认于
- 2025/11/04 03:31 4 个月前
函数中,为什么是这样???(见行)
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 条回复,欢迎继续交流。
正在加载回复...