欢迎访问~原文出处——
题意概括
一棵n个节点的树，每一个节点有一个权值，m次操作。
要支持操作有：删边、连边、区间求和、区间加、区间乘。
保证操作过程中不出现环。
n,m<=100000
题解
差不多是基础的LCT，加个懒标记。
2个懒标记，一个是乘的，一个是加的，下传的时候先乘后加。
注意用无符号的int，用LL会超时。
（数据较为友善，不卡无符号int）
代码
#include#include #include #include #include using namespace std;typedef long long LL;typedef unsigned int U;const int N=100005;const U Mod=51061;int n,m;int fa[N],son[N][2],rev[N];U sum[N],addt[N],addp[N],val[N],size[N];bool isd(char ch){ return '0'<=ch&&ch<='9';}void read(int &x){ char ch=getchar(); x=0; while (!isd(ch)) ch=getchar(); while (isd(ch)) x=x*10+ch-48,ch=getchar();}bool isroot(int x){ return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}void pushup(int x){ if (!x) return; sum[x]=(sum[son[x][0]]+sum[son[x][1]]+val[x])%Mod; size[x]=(size[son[x][0]]+size[son[x][1]]+1)%Mod;}void pushson(int x,U t,U p){ if (!x) return; addt[x]=addt[x]*t%Mod; addp[x]=(addp[x]*t+p)%Mod; val[x]=(val[x]*t+p)%Mod; sum[x]=(sum[x]*t+p*size[x])%Mod;}void pushdown(int x){ if (!x) return; int &ls=son[x][0],&rs=son[x][1]; if (rev[x]){ rev[x]=0; rev[ls]^=1; rev[rs]^=1; swap(ls,rs); } U &t=addt[x],&p=addp[x]; pushson(ls,t,p); pushson(rs,t,p); t=1,p=0;}void pushadd(int x){ if (!x) return; if (!isroot(x)) pushadd(fa[x]); pushdown(x);}int wson(int x){ return son[fa[x]][1]==x;}void rotate(int x){ if (isroot(x)) return; int y=fa[x],z=fa[y],L=wson(x),R=L^1; if (!isroot(y)) son[z][wson(y)]=x; fa[x]=z,fa[y]=x,fa[son[x][R]]=y; son[y][L]=son[x][R],son[x][R]=y; pushup(y); pushup(x);}void splay(int x){ pushadd(x); for (int y=fa[x];!isroot(x);rotate(x),y=fa[x]) if (!isroot(y)) rotate(wson(x)==wson(y)?y:x);}void access(int x){ int t=0; while (x){ splay(x); son[x][1]=t; pushup(x); t=x; x=fa[x]; }}void rever(int x){ access(x); splay(x); rev[x]^=1;}void link(int x,int y){ rever(x); fa[x]=y;}void cut(int x,int y){ rever(x); access(y); splay(y); fa[x]=son[y][0]=0;}int main(){ read(n),read(m); for (int i=1;i<=n;i++){ val[i]=sum[i]=size[i]=addt[i]=1; fa[i]=son[i][0]=son[i][1]=addp[i]=rev[i]=0; } for (int i=1,a,b;i