救救孩子!!
```cpp
#include <cstdio>
#define MOD 51061
#define N 100010
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
inline void swap(int&a,int&b){int tmp(a);a=b,b=tmp;}
int ch[N][2],fa[N],rev[N],sumv[N],addv[N],mulv[N],val[N],siz[N];
inline void up(int x)
{
sumv[x]=(sumv[lc(x)]+sumv[rc(x)]+val[x])%MOD;
siz[x]=siz[lc(x)]+siz[rc(x)]+1;
}
inline void add(int x,int v){val[x]=(val[x]+v)%MOD,addv[x]=(addv[x]+v)%MOD,sumv[x]=(sumv[x]+siz[x]*v)%MOD;}
inline void mul(int x,int v){val[x]=(long long)(val[x]*v)%MOD,addv[x]=(long long)(addv[x]*v)%MOD,mulv[x]=(long long)(mulv[x]*v)%MOD,sumv[x]=(long long)(sumv[x]*v)%MOD;}
inline void down(int x)
{
if(rev[x])
rev[lc(x)]^=1,rev[rc(x)]^=1,swap(lc(x),rc(x)),rev[x]=0;
if(mulv[x]!=1)
mul(lc(x),mulv[x]),mul(rc(x),mulv[x]),mulv[x]=1;
if(addv[x])
add(lc(x),addv[x]),add(rc(x),addv[x]),addv[x]=0;
}
inline int nrt(int x){return x==lc(fa[x])||x==rc(fa[x]);}
void psa(int x){if(nrt(x))psa(fa[x]);down(x);}
inline void rotate(int x)
{
int y(fa[x]),z(fa[y]),k(x==rc(y));
ch[y][k]=ch[x][!k],ch[x][!k]=y;if(nrt(y))ch[z][y==rc(z)]=x;
if(ch[y][k])fa[ch[y][k]]=y;fa[y]=x,fa[x]=z;
up(y),up(x);
}
inline void splay(int x)
{
int y,z;
for(psa(x);nrt(x);rotate(x))
{y=fa[x],z=fa[y];if(nrt(y))rotate(x==rc(y)^y==rc(z)?x:y);}
}
inline void access(int x){for(int y(0);x;x=fa[y=x])splay(x),rc(x)=y,up(x);}
inline void mrt(int x){access(x),splay(x),rev[x]^=1;}
inline void link(int x,int y){mrt(x),fa[x]=y;}
inline void cut(int x,int y){mrt(x),access(y),splay(y),fa[x]=lc(y)=0;}
inline int query(int x,int y){mrt(x),access(y),splay(y);return sumv[y];}
int n,q,x,y,p,t;
char opt;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)
val[i]=siz[i]=mulv[i]=1;
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
link(x,y);
}
while(q--)
{
scanf("\n%c%d%d",&opt,&x,&y);
switch(opt)
{
case'+':mrt(x),access(y),splay(y);scanf("%d",&p);add(y,p);break;
case'-':scanf("%d%d",&p,&t);cut(x,y),link(p,t);break;
case'*':mrt(x),access(y),splay(y);scanf("%d",&p);mul(y,p);break;
case'/':printf("%d\n",query(x,y));
}
}
return 0;
}
```
by yurzhang @ 2019-02-01 19:32:21
%%%
by kkksx @ 2019-02-01 19:33:17
orz tql
[这是我的记录,希望对你有帮助](https://www.luogu.org/recordnew/show/15934285)
by 梧桐灯 @ 2019-02-01 19:38:42
@[光随影走](/space/show?uid=31193) emmm谢谢,不过5分的我并不能看提交记录的代码
by yurzhang @ 2019-02-01 19:51:39
@[yurzhang](/space/show?uid=126486) 你splay后没有update
by 梧桐灯 @ 2019-02-01 20:03:27
@[光随影走](/space/show?uid=31193) 但是我rotate的时候update了呀,这样不行吗
by yurzhang @ 2019-02-01 20:06:10
@[yurzhang](/space/show?uid=126486) 不一定行啊,
splay里
```cpp
{y=fa[x],z=fa[y];
if(nrt(y))
rotate(x==rc(y)^y==rc(z)?x:y);}
```
这个循环判断后应该加upd(x),这个你在rot里体现了,但循环结束后还应该再来一次upd(x)
by 梧桐灯 @ 2019-02-01 20:10:11
```cpp
void rot (int x) {
int y = fa[x];
int r = fa[y];
int ys = ch[y][1] == x;
int rs = ch[x][!ys];
if (nr (y)) ch[r][ch[r][1] == y] = x;
ch[x][!ys] = y;
ch[y][ys] = rs;
if (rs) fa[rs] = y;
fa[y] = x;
fa[x] = r;
upd (y);
return ;
}
```
```cpp
void splay (int x) {
int y = x, z = 0;
st[++z] = y;
while (nr (y)) st[++z] = y = fa[y];
while (z) pd (st[z--]);
while (nr (x)) {
y = fa[x]; z = fa[y];
if (nr (y)) rot ((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
rot (x);
}
upd (x);
return ;
}
```
这是我的写法
by 梧桐灯 @ 2019-02-01 20:10:57
@[光随影走](/space/show?uid=31193) 但我的update里把y和x都upd了一遍,splay最后rotate(x)的时候应该最后会upd(x)的啊
by yurzhang @ 2019-02-02 10:54:41