传送门

分析

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

lct板子题

单独维护一下加和乘的情况即可

维护方法和维护翻转差不多

代码

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<queue> #include<ctime> #include<vector> #include<set> #include<map> #include<stack>
using namespace std; #define add(x,y) x=(x+y)%mod;
#define mul(x,y) x=1ll*x*y%mod;
const int mod = 51061; int  n,q,fa[100100],son[100100][2],sum[100100],siz[100100]; int cola[100100],colm[100100],a[100100],r[100100]; inline void up(int x){ sum[x]=(sum[son[x][0]]+sum[son[x][1]]+a[x])%mod; siz[x]=(siz[son[x][0]]+siz[son[x][1]]+1)%mod; } inline void rev(int x){swap(son[x][0],son[x][1]);r[x]^=1;} inline void doa(int x,int y){ add(a[x],y); add(sum[x],1ll*siz[x]*y%mod); add(cola[x],y); } inline void dom(int x,int y){ mul(a[x],y); mul(sum[x],y); mul(cola[x],y); mul(colm[x],y); } inline void pd(int x){ if(colm[x]!=1){ dom(son[x][0],colm[x]); dom(son[x][1],colm[x]); colm[x]=1; } if(cola[x]){ doa(son[x][0],cola[x]); doa(son[x][1],cola[x]); cola[x]=0; } if(r[x]){ if(son[x][0])rev(son[x][0]); if(son[x][1])rev(son[x][1]); r[x]=0; } } inline bool notroot(int x){return x==son[fa[x]][0]||x==son[fa[x]][1];} inline void push_all(int x){if(notroot(x))push_all(fa[x]);pd(x);} inline int gs(int x){return son[fa[x]][1]==x;} inline void rot(int x){ int y=fa[x],z=fa[y],b=gs(x),c=gs(y),d=son[x][!b]; if(notroot(y))son[z][c]=x; fa[x]=z; if(d)fa[d]=y; son[y][b]=d; son[x][!b]=y; fa[y]=x; up(y),up(x); } inline void splay(int x){ push_all(x); while(notroot(x)){ int y=fa[x],z=fa[y]; if(notroot(y)){ if(gs(x)==gs(y))rot(y); else rot(x); } rot(x); } } inline void access(int x){ for(int y=0;x;y=x,x=fa[x]) splay(x),son[x][1]=y,up(x); } inline void makeroot(int x){ access(x); splay(x); rev(x); } inline int findroot(int x){ access(x); splay(x); while(son[x][0])pd(x),x=son[x][0]; return x; } inline void spt(int x,int y){ makeroot(x); access(y); splay(y); } inline void link(int x,int y){ makeroot(x); if(findroot(y)!=x)fa[x]=y; } inline void cut(int x,int y){ makeroot(x); if(findroot(y)==x&&fa[x]==y&&(!son[x][1])) fa[x]=son[y][0]=0,up(y); } int main(){ int i,j,k; scanf("%d%d",&n,&q); for(i=1;i<=n;i++)siz[i]=sum[i]=a[i]=1; for(i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); link(x,y); } for(i=1;i<=q;i++){ char s[3]; int x,y,z,w; scanf("%s",s); if(s[0]=='+'){ scanf("%d%d%d",&x,&y,&z); spt(x,y); doa(y,z); }else if(s[0]=='-'){ scanf("%d%d%d%d",&x,&y,&z,&w); cut(x,y); link(z,w); }else if(s[0]=='*'){ scanf("%d%d%d",&x,&y,&z); spt(x,y); dom(y,z); }else { scanf("%d%d",&x,&y); spt(x,y); printf("%d\n",sum[y]); } } return 0; }
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄