Description
一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：
+ u v c：将u到v的路径上的点的权值都加上自然数c；
- u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；
* u v c：将u到v的路径上的点的权值都乘上自然数c；
/ u v：询问u到v的路径上的点的权值和，求出答案对于51061的余数。
Input
第一行两个整数n，q
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
Output
对于每个/对应的答案输出一行
Sample Input
3 2
1 2
2 3
* 1 3 4
/ 1 1
1 2
2 3
* 1 3 4
/ 1 1
Sample Output
4
解题思路：
假如没有2操作，且图是树，是不是想起了线段树。
这道题也是一样的道理，LCT嘛，splay维护树链
代码：
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll tr[spc].ch[0]
#define rrr tr[spc].ch[1]
#define ls ch[0]
#define rs ch[1]
typedef unsigned int lnt;
const lnt mod=;
struct trnt{
int ch[];
int fa;
int lzt;
lnt add;
lnt mul;
lnt sum;
lnt wgt;
lnt val;
bool anc;
}tr[];
int st[];
int tp;
int n,q;
char cmd[];
int read()
{
int f=,x=;
char ss=getchar();
while(ss<''||ss>''){if(ss=='-')f=-;ss=getchar();}
while(ss>=''&&ss<=''){x=x*+ss-'';ss=getchar();}
return f*x;
}
int comd(void)
{
if(cmd[]=='+')
return ;
if(cmd[]=='-')
return ;
if(cmd[]=='*')
return ;
if(cmd[]=='/')
return ;
return ;
}
bool whc(int spc)
{
return tr[tr[spc].fa].rs==spc;
}
void pushup(int spc)
{
tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+;
tr[spc].sum=(tr[lll].sum+tr[rrr].sum+tr[spc].val)%mod;
}
void trr(int spc)
{
if(!spc)
return ;
tr[spc].lzt^=;
std::swap(lll,rrr);
}
void Mul(int spc,lnt k)
{
if(!spc)
return ;
tr[spc].add=tr[spc].add*k%mod;
tr[spc].sum=tr[spc].sum*k%mod;
tr[spc].val=tr[spc].val*k%mod;
tr[spc].mul=tr[spc].mul*k%mod;
}
void Add(int spc,lnt k)
{
if(!spc)
return ;
if(tr[spc].mul)
{
Mul(lll,tr[spc].mul);
Mul(rrr,tr[spc].mul);
tr[spc].mul=;
}
tr[spc].sum=(tr[spc].sum+tr[spc].wgt*k)%mod;
tr[spc].val=(tr[spc].val+k)%mod;
tr[spc].add=(tr[spc].add+k)%mod;
}
void pushdown(int spc)
{
if(tr[spc].lzt)
{
tr[spc].lzt=;
trr(lll);
trr(rrr);
}
if(tr[spc].mul!=)
{
Mul(lll,tr[spc].mul);
Mul(rrr,tr[spc].mul);
tr[spc].mul=;
}
if(tr[spc].add)
{
Add(lll,tr[spc].add);
Add(rrr,tr[spc].add);
tr[spc].add=;
}
}
void rotate(int spc)
{
int f=tr[spc].fa;
bool k=whc(spc);
tr[f].ch[k]=tr[spc].ch[!k];
tr[spc].ch[!k]=f;
if(tr[f].anc)
{
tr[spc].anc=;
tr[f].anc=;
}else
tr[tr[f].fa].ch[whc(f)]=spc;
tr[spc].fa=tr[f].fa;
tr[f].fa=spc;
tr[tr[f].ch[k]].fa=f;
pushup(f);
pushup(spc);
}
void splay(int spc)
{
tp=;
int x=spc;
while(!tr[x].anc)
st[++tp]=x,x=tr[x].fa;
st[++tp]=x;
while(tp)
pushdown(st[tp--]);
while(!tr[spc].anc)
{
int ft=tr[spc].fa;
if(tr[ft].anc)
{
rotate(spc);
return ;
}
if(whc(spc)^whc(ft))
rotate(spc);
else
rotate(ft);
rotate(spc);
}
pushup(spc);
}
void access(int spc)
{
int lst=;
while(spc)
{
splay(spc);
tr[rrr].anc=;
tr[lst].anc=;
rrr=lst;
pushup(spc);
lst=spc;
spc=tr[spc].fa;
}
}
void Mtr(int spc)
{
access(spc);
splay(spc);
trr(spc);
}
void split(int x,int y)
{
Mtr(x);
access(y);
splay(y);
}
void link(int x,int y)
{
Mtr(x);
tr[x].fa=y;
}
void cut(int x,int y)
{
split(x,y);
tr[y].ls=;
tr[x].fa=;
tr[x].anc=;
pushup(y);
}
int main()
{
n=read();
q=read();
for(int i=;i<=n;i++)
{
tr[i].anc=;
tr[i].mul=;
tr[i].val=;
tr[i].wgt=tr[i].sum=;
}
for(int i=;i<n;i++)
{
int a=read(),b=read();
link(a,b);
}
while(q--)
{
scanf("%s",cmd);
int opt=comd();
if(opt==)
{
int u=read(),v=read(),c=read();
split(u,v);
Add(v,c);
}
if(opt==)
{
int ua=read(),va=read(),ub=read(),vb=read();
cut(ua,va);
link(ub,vb);
}
if(opt==)
{
int u=read(),v=read(),c=read();
split(u,v);
Mul(v,c);
}
if(opt==)
{
int u=read(),v=read();
split(u,v);
printf("%u\n",tr[v].sum);
}
}
return ;
}