1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "rb", stdin);freopen(#x".out", "w+", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
return data*w;
}
const int maxn(100010), mod(51061);
int n, q;
int val[maxn], sum[maxn], lzmul[maxn], lzadd[maxn], fa[maxn], son[2][maxn], st[maxn], top, size[maxn];
bool rev[maxn];
inline bool isroot(int x) { return son[0][fa[x]]!=x && son[1][fa[x]]!=x; }
inline bool get_son(int x) { return son[1][fa[x]]==x; }
inline void update(int x) { sum[x]=(1ll*sum[son[0][x]]+sum[son[1][x]]+val[x])%mod; size[x]=size[son[0][x]]+size[son[1][x]]+1; }
inline void psmul(int x, int v)
{
if(x==0) return;
sum[x]=1ll*sum[x]*v%mod;
lzmul[x]=1ll*lzmul[x]*v%mod;
val[x]=1ll*val[x]*v%mod;
lzadd[x]=1ll*lzadd[x]*v%mod;
}
inline void psadd(int x, int v)
{
if(x==0) return;
sum[x]=(1ll*sum[x]+1ll*size[x]*v)%mod;
val[x]=(1ll*val[x]+v)%mod;
lzadd[x]=(1ll*lzadd[x]+v)%mod;
}
inline void pushdown(int x)
{
if(lzmul[x]!=1) psmul(son[0][x], lzmul[x]), psmul(son[1][x], lzmul[x]), lzmul[x]=1;
if(lzadd[x]) psadd(son[0][x], lzadd[x]), psadd(son[1][x], lzadd[x]), lzadd[x]=0;
if(rev[x])
{
if(son[0][x]) rev[son[0][x]]^=1;
if(son[1][x]) rev[son[1][x]]^=1;
rev[x]=0;
swap(son[0][x], son[1][x]);
}
}
inline void rotate(int x)
{
int f=fa[x], g=fa[f], l=get_son(x), r=l^1;
if(!isroot(f)) son[get_son(f)][g]=x;
fa[x]=g; fa[f]=x; fa[son[r][x]]=f;
son[l][f]=son[r][x]; son[r][x]=f;
update(f); update(x);
}
inline void splay(int x)
{
top=1; st[top]=x;
for(RG int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
for(RG int i=top;i;i--) pushdown(st[i]);
for(;!isroot(x);rotate(x)) if(!isroot(fa[x])) rotate(get_son(fa[x])^get_son(x)?x:fa[x]);
}
inline void access(int x) { for(RG int t=0;x;t=x, x=fa[x]) splay(x), son[1][x]=t, update(x); }
inline void makeroot(int x) { access(x); splay(x); rev[x]^=1; }
inline void split(int x, int y) { makeroot(x); access(y); splay(y); }
inline void link(int x, int y) { makeroot(x); fa[x]=y; }
inline void cut(int x, int y) { split(x, y); if(son[0][y]==x) son[0][y]=0; fa[x]=0; }
inline void mul(int x, int y, int v) { split(x, y); psmul(y, v); }
inline void add(int x, int y, int v) { split(x, y); psadd(y, v); }
inline int query(int x, int y) { split(x, y); return sum[y]; }
int a, b, c, d;
char s[3];
int main()
{
n=read(); q=read();
for(RG int i=1;i<=n;i++) val[i]=size[i]=lzmul[i]=1;
for(RG int i=1;i<n;i++) a=read(), b=read(), link(a, b);
while(q--)
{
scanf("%s", s);
a=read(); b=read();
if(s[0]=='+') c=read(), add(a, b, c);
else if(s[0]=='-') c=read(), d=read(), cut(a, b), link(c, d);
else if(s[0]=='*') c=read(), mul(a, b, c);
else printf("%d\n", query(a, b));
}
return 0;
}
|