Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,q;

#define MAXN 100010

#define MOD 51061

struct node

{

	int c[2],fa,siz;

	unsigned int sum,val,add,mul;

	node(){c[0] = c[1] = fa = sum = val = add = mul = siz = 0;}

	bool rev;

}t[MAXN];

int ptr = 0;

inline int newnode(){return ++ptr;}

inline void maintain(int rt)

{

	t[rt].sum = t[rt].val;t[rt].siz = 1;

	if(t[rt].c[0] != 0)

	{

		t[rt].sum = (t[rt].sum + t[t[rt].c[0]].sum) % MOD;

		t[rt].siz = t[rt].siz + t[t[rt].c[0]].siz;

	}

	if(t[rt].c[1] != 0)

	{

		t[rt].sum = (t[rt].sum + t[t[rt].c[1]].sum) % MOD;

		t[rt].siz = t[rt].siz + t[t[rt].c[1]].siz;

	}

	return;

}

inline void pushdown(int k)

{

	if(t[k].rev)

	{

		t[t[k].c[0]].rev ^= 1;t[t[k].c[1]].rev ^= 1;

		swap(t[k].c[0],t[k].c[1]);t[k].rev = false;

	}

	t[t[k].c[0]].sum = (t[t[k].c[0]].sum * t[k].mul % MOD + t[k].add * t[t[k].c[0]].siz % MOD) % MOD;

	t[t[k].c[0]].val = (t[t[k].c[0]].val * t[k].mul % MOD + t[k].add) % MOD;

	t[t[k].c[0]].mul = t[t[k].c[0]].mul * t[k].mul % MOD;

	t[t[k].c[0]].add = (t[t[k].c[0]].add * t[k].mul % MOD + t[k].add) % MOD;

	t[t[k].c[1]].sum = (t[t[k].c[1]].sum * t[k].mul % MOD + t[k].add * t[t[k].c[1]].siz % MOD) % MOD;

	t[t[k].c[1]].val = (t[t[k].c[1]].val * t[k].mul % MOD + t[k].add) % MOD;

	t[t[k].c[1]].mul = t[t[k].c[1]].mul * t[k].mul % MOD;

	t[t[k].c[1]].add = (t[t[k].c[1]].add * t[k].mul % MOD + t[k].add) % MOD;

	t[k].mul = 1;t[k].add = 0;

	return;

}

inline bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

inline int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

inline void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;}

inline void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

stack<int> s;

inline void splay(int x)

{

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

inline void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

inline void makeroot(int x){access(x);splay(x);t[x].rev ^= 1;return;}

void link(int x,int y){makeroot(x);t[x].fa = y;return;}

void cut(int x,int y){makeroot(x);access(y);splay(y);t[x].fa = t[y].c[0] = 0;maintain(y);return;}







char getc()

{

	register char c = getchar();

	while(c != '+' && c != '-' && c != '*' && c != '/')c = getchar();

	return c;

}

int main()

{

	scanf("%d%d",&n,&q);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		link(a,b);

	}

	for(int i = 1;i <= n;++i)t[i].sum = t[i].siz = t[i].val = 1;

	int w,x,y,z;

	char c;

	for(int i = 1;i <= q;++i)

	{

		c = getc();

		switch (c)

		{

			case '+':

			{

				scanf("%d%d%d",&a,&b,&w);w %= MOD;

				makeroot(a);access(b);splay(b);

				t[b].val = (t[b].val + w) % MOD;t[b].add = (t[b].add + w) % MOD;

				t[b].sum = (t[b].sum + w * t[b].siz) % MOD;

				break;

			}

			case '-':

			{

				scanf("%d%d%d%d",&a,&b,&x,&y);

				cut(a,b);link(x,y);

				break;

			}

			case '*':

			{

				scanf("%d%d%d",&a,&b,&w);w %= MOD;

				makeroot(a);access(b);splay(b);

				t[b].val = (t[b].val * w) % MOD;t[b].add = (t[b].add * w) % MOD;

				t[b].mul = (t[b].mul * w) % MOD;t[b].sum = (t[b].sum * w) % MOD;

				break;

			}

			case '/':

			{

				scanf("%d%d",&a,&b);

				makeroot(a),access(b);splay(b);

				printf("%u\n",t[b].sum);

				break;

			}

		}

	}

	return 0;

}