下面是代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
#define MOD 51061
using namespace std;
int n,m,w[MAXN];
struct node{
int son[2];
int f,v,flag,c,d,s;
node(){
flag=c=0;
v=d=s=1;
}
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline bool isroot(int rt){
return a[a[rt].f].son[0]!=rt&&a[a[rt].f].son[1]!=rt;
}
inline void pushup(int rt){
if(!rt)return;
a[rt].v=(a[a[rt].son[0]].v%MOD+a[a[rt].son[1]].v%MOD+w[rt]%MOD)%MOD;
a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+1;
}
inline void update1(int rt,int k){
if(!rt)return;
w[rt]=(w[rt]+k)%MOD;
a[rt].v=(a[rt].v+k*a[rt].s)%MOD;
a[rt].c=(a[rt].c+k)%MOD;
}
inline void update2(int rt,int k){
if(!rt)return;
w[rt]=(w[rt]*k)%MOD;
a[rt].v=(a[rt].v*k)%MOD;
a[rt].d=(a[rt].d*k)%MOD;
a[rt].c=(a[rt].c*k)%MOD;
}
inline void pushdown(int rt){
if(!rt)return;
if(a[rt].flag){
a[a[rt].son[0]].flag^=1;a[a[rt].son[1]].flag^=1;
swap(a[rt].son[0],a[rt].son[1]);
a[rt].flag=0;
}
if(a[rt].d!=1){
update2(a[rt].son[0],a[rt].d);update2(a[rt].son[1],a[rt].d);
a[rt].d=1;
}
if(a[rt].c){
update1(a[rt].son[0],a[rt].c);update1(a[rt].son[1],a[rt].c);
a[rt].c=0;
}
}
inline void turn(int rt){
int x=a[rt].f,y=a[x].f,k=a[x].son[0]==rt?1:0;
pushdown(x);pushdown(rt);
if(!isroot(x)){
if(a[y].son[0]==x)a[y].son[0]=rt;
else a[y].son[1]=rt;
}
a[rt].f=y;a[x].f=rt;a[a[rt].son[k]].f=x;
a[x].son[k^1]=a[rt].son[k];a[rt].son[k]=x;
pushup(x);pushup(rt);
}
void splay(int rt){
int top=0,stack[MAXN];
stack[++top]=rt;
for(int i=rt;!isroot(i);i=a[i].f)stack[++top]=a[i].f;
while(top)pushdown(stack[top--]);
while(!isroot(rt)){
int x=a[rt].f,y=a[x].f;
if(!isroot(x)){
if((a[x].son[0]==rt)^(a[y].son[0]==x))turn(rt);
else turn(x);
}
turn(rt);
}
pushup(rt);
}
void access(int rt){
for(int i=0;rt;i=rt,rt=a[rt].f){
splay(rt);
a[rt].son[1]=i;
pushup(rt);
}
}
inline void makeroot(int rt){access(rt);splay(rt);a[rt].flag^=1;}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline void cut(int x,int y){split(x,y);a[y].son[0]=a[x].f=0;}
inline void link(int x,int y){makeroot(x);a[x].f=y;access(x);splay(x);}
int main(){
char ch[2];
int x,y,k;
n=read();m=read();
for(int i=1;i<=n;i++)w[i]=1;
for(int i=1;i<n;i++){
x=read();y=read();
link(x,y);
}
while(m--){
scanf("%s",ch);x=read();y=read();
switch(ch[0]){
case '+':{
k=read();
split(x,y);
update1(y,k);
break;
}
case '-':{
cut(x,y);
x=read();y=read();
link(x,y);
break;
}
case '*':{
k=read();
split(x,y);
update2(y,k);
break;
}
case '/':{
split(x,y);
printf("%d\n",a[y].v);
break;
}
}
}
return 0;
}
```
by 斯德哥尔摩 @ 2018-02-10 22:39:34
额，我好像把所有能 pushdown 的地方都 pushdown 了一下，然后就过了。。。
LCT 真是个神奇的东东。。。
此贴已结。。。
by 斯德哥尔摩 @ 2018-02-10 23:38:48
Orz
by Dispwnl @ 2018-03-19 07:24:07
#include<cstdio>
#include<cstdlib>
#define R register unsigned int
#define I inline
#define YL 51061
#define lc c[x][0]
#define rc c[x][1]
#define mul(x) x*=c;x%=YL
#define add(x,c) x+=c;x%=YL
#define G ch=getchar()
#define gc G;while(ch<'*')G
#define in(z) gc;z=ch&15;G;while(ch>'*')z*=10,z+=ch&15,G;
const int N=100009;
unsigned int n,f[N],c[N][2],v[N],s[N],sz[N],lm[N],la[N],st[N];
bool r[N];
I bool nroot(R x){
return c[f[x]][0]==x||c[f[x]][1]==x;
}
I void pushup(R x){
s[x]=(s[lc]+s[rc]+v[x])%YL;
sz[x]=sz[lc]+sz[rc]+1;
}
I void pushr(R x){
R t=lc;lc=rc;rc=t;r[x]^=1;
}
I void pushm(R x,R c){
mul(s[x]);mul(v[x]);mul(lm[x]);mul(la[x]);
}
I void pusha(R x,R c){
add(s[x],c*sz[x]);add(v[x],c);add(la[x],c);
}
I void pushdown(R x){
if(lm[x]!=1)pushm(lc,lm[x]),pushm(rc,lm[x]),lm[x]=1;
if(la[x]) pusha(lc,la[x]),pusha(rc,la[x]),la[x]=0;
if(r[x]) {if(lc)pushr(lc);if(rc)pushr(rc);r[x]=0;}
}
I void rotate(R x){
R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
if(w)f[w]=y;f[y]=x;f[x]=z;
pushup(y);
}
I void splay(R x){
R y=x,z=0;
st[++z]=y;
while(nroot(y))st[++z]=y=f[y];
while(z)pushdown(st[z--]);
while(nroot(x)){
y=f[x];z=f[y];
if(nroot(y))
rotate((c[y][0]==x)^(c[z][0]==y)?y:x);
rotate(x);
}
pushup(x);
}
I void access(R x){
for(R y=0;x;x=f[y=x])
splay(x),rc=y,pushup(x);
}
I void makeroot(R x){
access(x);
splay(x);
pushr(x);
}
I void split(R x,R y){
makeroot(x);
access(y);
splay(y);
}
I void link(R x,R y){
makeroot(x);f[x]=y;
}
I void cut(R x,R y){
split(x,y);f[x]=c[y][0]=0;
}
int main()
{
register char ch;
R q,i,a,b,k;
in(n);in(q);
for(i=1;i<=n;++i)v[i]=sz[i]=lm[i]=1;
for(i=1;i<n;++i){
in(a);in(b);
link(a,b);
}
while(q--){
gc;
switch(ch){
case '+':
in(a);in(b);in(k);
split(a,b);pusha(b,k);
break;
case '-':
in(a);in(b);cut(a,b);
in(a);in(b);link(a,b);
break;
case '*':
in(a);in(b);in(k);
split(a,b);pushm(b,k);
break;
case '/':
in(a);in(b);
split(a,b);
printf("%d\n",s[b]);
}
}
return 0;
}
by うちはサスケ @ 2018-12-16 19:47:30
```c
#include<cstdio>
#include<cstdlib>
#define R register unsigned int
#define I inline
#define YL 51061
#define lc c[x][0]
#define rc c[x][1]
#define mul(x) x*=c;x%=YL
#define add(x,c) x+=c;x%=YL
#define G ch=getchar()
#define gc G;while(ch<'*')G
#define in(z) gc;z=ch&15;G;while(ch>'*')z*=10,z+=ch&15,G;
const int N=100009;
unsigned int n,f[N],c[N][2],v[N],s[N],sz[N],lm[N],la[N],st[N];
bool r[N];
I bool nroot(R x){
return c[f[x]][0]==x||c[f[x]][1]==x;
}
I void pushup(R x){
s[x]=(s[lc]+s[rc]+v[x])%YL;
sz[x]=sz[lc]+sz[rc]+1;
}
I void pushr(R x){
R t=lc;lc=rc;rc=t;r[x]^=1;
}
I void pushm(R x,R c){
mul(s[x]);mul(v[x]);mul(lm[x]);mul(la[x]);
}
I void pusha(R x,R c){
add(s[x],c*sz[x]);add(v[x],c);add(la[x],c);
}
I void pushdown(R x){
if(lm[x]!=1)pushm(lc,lm[x]),pushm(rc,lm[x]),lm[x]=1;
if(la[x]) pusha(lc,la[x]),pusha(rc,la[x]),la[x]=0;
if(r[x]) {if(lc)pushr(lc);if(rc)pushr(rc);r[x]=0;}
}
I void rotate(R x){
R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
if(w)f[w]=y;f[y]=x;f[x]=z;
pushup(y);
}
I void splay(R x){
R y=x,z=0;
st[++z]=y;
while(nroot(y))st[++z]=y=f[y];
while(z)pushdown(st[z--]);
while(nroot(x)){
y=f[x];z=f[y];
if(nroot(y))
rotate((c[y][0]==x)^(c[z][0]==y)?y:x);
rotate(x);
}
pushup(x);
}
I void access(R x){
for(R y=0;x;x=f[y=x])
splay(x),rc=y,pushup(x);
}
I void makeroot(R x){
access(x);
splay(x);
pushr(x);
}
I void split(R x,R y){
makeroot(x);
access(y);
splay(y);
}
I void link(R x,R y){
makeroot(x);f[x]=y;
}
I void cut(R x,R y){
split(x,y);f[x]=c[y][0]=0;
}
int main()
{
register char ch;
R q,i,a,b,k;
in(n);in(q);
for(i=1;i<=n;++i)v[i]=sz[i]=lm[i]=1;
for(i=1;i<n;++i){
in(a);in(b);
link(a,b);
}
while(q--){
gc;
switch(ch){
case '+':
in(a);in(b);in(k);
split(a,b);pusha(b,k);
break;
case '-':
in(a);in(b);cut(a,b);
in(a);in(b);link(a,b);
break;
case '*':
in(a);in(b);in(k);
split(a,b);pushm(b,k);
break;
case '/':
in(a);in(b);
split(a,b);
printf("%d\n",s[b]);
}
}
return 0;
}
```
by うちはサスケ @ 2018-12-16 19:47:50