这个题一看就是裸地LCT嘛，但是我wa了好几遍，这秘制标记......
注意事项：I.*对+有贡献 II.先下传*再下传+（因为我们已经维护了+，不能再让*对+产生贡献）III.维护+用到size
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 100005
#define P 51061
using namespace std;
inline unsigned int read()
{
unsigned int sum=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')
{
sum=(sum<<)+(sum<<)+ch-'';
ch=getchar();
}
return sum;
}
struct LCT
{
struct Node
{
Node *ch[],*f;
unsigned int key,multi,pluss,sum,size;
bool rev;
void pushup()
{
sum=(key+ch[]->sum+ch[]->sum)%P;
size=ch[]->size++ch[]->size;
}
}null[MAXN];
void swap(Node *&x,Node *&y)
{
Node *temp=x;
x=y;
y=temp;
}
void pushdown(Node *p)
{
if(p->rev)
{
p->ch[]->rev^=;
p->ch[]->rev^=;
swap(p->ch[],p->ch[]);
p->rev=;
}
if(p->multi!=)
{
p->ch[]->sum=(p->ch[]->sum*p->multi)%P;
p->ch[]->key=(p->ch[]->key*p->multi)%P;
p->ch[]->pluss=(p->ch[]->pluss*p->multi)%P;
p->ch[]->multi=(p->ch[]->multi*p->multi)%P;
p->ch[]->sum=(p->ch[]->sum*p->multi)%P;
p->ch[]->key=(p->ch[]->key*p->multi)%P;
p->ch[]->pluss=(p->ch[]->pluss*p->multi)%P;
p->ch[]->multi=(p->ch[]->multi*p->multi)%P;
p->multi=;
}
if(p->pluss)
{
if(p->ch[]!=null)
{
p->ch[]->sum=(p->ch[]->sum+p->pluss*p->ch[]->size)%P;
p->ch[]->key=(p->ch[]->key+p->pluss)%P;
p->ch[]->pluss=(p->ch[]->pluss+p->pluss)%P;
}
if(p->ch[]!=null)
{
p->ch[]->sum=(p->ch[]->sum+p->pluss*p->ch[]->size)%P;
p->ch[]->key=(p->ch[]->key+p->pluss)%P;
p->ch[]->pluss=(p->ch[]->pluss+p->pluss)%P;
}
p->pluss=;
}
}
void Init()
{
null->ch[]=null->ch[]=null->f=null;
for(unsigned int i=;i<MAXN;i++)
null[i].ch[]=null[i].ch[]=null[i].f=null,null[i].sum=null[i].key=null[i].multi=,null[i].pluss=;
}
bool isroot(Node *p)
{
return p->f->ch[]!=p&&p->f->ch[]!=p;
}
unsigned int get(Node *p)
{
return p->f->ch[]==p;
}
void rotate(Node *p)
{
Node *fa=p->f,*pa=fa->f;
unsigned int j=get(p);
if(!isroot(fa))pa->ch[get(fa)]=p;
if((fa->ch[j]=p->ch[j^])!=null)fa->ch[j]->f=fa;
fa->f=p;
p->f=pa;
p->ch[j^]=fa;
fa->pushup();
p->pushup();
}
void spaly(Node *p)
{
pushdown(p);
for(Node *fa=p->f;!isroot(p);rotate(p),fa=p->f)
if(!isroot(fa))
{
pushdown(fa->f),pushdown(fa),pushdown(p);
rotate(get(fa)==get(p)?fa:p);
}
else
pushdown(fa),pushdown(p);
}
void expose(Node *x)
{
Node *y=null;
while(x!=null)
{
spaly(x);
x->ch[]=y;
x->pushup();
y=x;
x=x->f;
}
}
void make_root(Node *p)
{
expose(p);
spaly(p);
p->rev^=;
}
void cut(unsigned int a,unsigned int b)
{
Node *x=null+a,*y=null+b;
make_root(x);
expose(y);
spaly(y);
y->ch[]->f=null;
y->ch[]=null;
y->pushup();
}
void link(unsigned int a,unsigned int b)
{
Node *x=null+a,*y=null+b;
make_root(x);
x->f=y;
}
void up(unsigned int a,unsigned int b,unsigned int c)
{
Node *x=null+a,*y=null+b;
make_root(x);
expose(y);
spaly(y);
y->pluss=(y->pluss+c)%P;
y->key=(y->key+c)%P;
y->sum=(y->sum+y->size*c)%P;
}
void UUP(unsigned int a,unsigned int b,unsigned int c)
{
Node *x=null+a,*y=null+b;
make_root(x);
expose(y);
spaly(y);
y->multi=(y->multi*c)%P;
y->key=(y->key*c)%P;
y->sum=(y->sum*c)%P;
y->pluss=(y->pluss*c)%P;
}
unsigned int query(unsigned int a,unsigned int b)
{
Node *x=null+a,*y=null+b;
make_root(x);
expose(y);
spaly(y);
return y->sum;
}
}YY;
int main()
{
YY.Init();
unsigned int n=read(),m=read();
for(unsigned int i=;i<n;i++)
{
unsigned int x=read(),y=read();
YY.link(x,y);
}
for(unsigned int i=,x,y,z,a,b;i<=m;i++)
{
char ch;
cin>>ch;
x=read(),y=read();
switch(ch)
{
case '*':z=read();
YY.UUP(x,y,z);
break;
case '+':z=read();
YY.up(x,y,z);
break;
case '-':a=read(),b=read();
YY.cut(x,y);
YY.link(a,b);
break;
case '/':printf("%d\n",YY.query(x,y));
break;
}
}
return ;
}