链接：https://www.luogu.org/problemnew/show/P1501
题面：
题目描述
一棵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的余数。
输入输出格式
输入格式：
第一行两个整数n，q
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
输出格式：
对于每个/对应的答案输出一行
输入输出样例
输入样例#1：
3 2
1 2
2 3
* 1 3 4
/ 1 1
输出样例#1：
4
说明
10%的数据保证，1<=n，q<=2000
另外15%的数据保证，1<=n，q<=5*10^4，没有-操作，并且初始树为一条链
另外35%的数据保证，1<=n，q<=5*10^4，没有-操作
100%的数据保证，1<=n，q<=10^5，0<=c<=10^4
By (伍一鸣)
思路：
写法跟线段树差不多，修改i下pushdown多维护连个标记就好了。
实现代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ls c[x][0]
#define rs c[x][1]
const int M = 4e5+;
const int inf = 1e9;
const int mod = ;
int top;
int sum[M],c[M][],val[M],fa[M],rev[M],mn[M],S[M],tmp[M];
int siz[M],mul[M],add[M];
inline void up(int x){
//cout<<sum[x]<<" "<<sum[ls]<<" "<<sum[rs]<<" "<<val[x]<<endl;
sum[x] = (sum[ls] + sum[rs] + val[x])%mod;
siz[x] = (siz[ls] + siz[rs] + )%mod;;
} inline void pushrev(int x){
swap(ls,rs); rev[x] ^= ;
} inline void pushmul(int x,int c){
mul[x] = (1LL*mul[x]*c)%mod;
add[x] = (1LL*add[x]*c)%mod;
sum[x] = (1LL*sum[x]*c)%mod;
val[x] = (1LL*val[x]*c)%mod;
//cout<<mul[x]<<" "<<val[x]<<endl;
} inline void pushadd(int x,int c){
add[x] = (add[x] + c)%mod;
val[x] = (val[x] + c)%mod;
sum[x] = (1LL*sum[x]+1LL*siz[x]*c)%mod;
} inline bool isroot(int x){
return c[fa[x]][]!=x&&c[fa[x]][]!=x;
} inline void rotate(int x){
int y = fa[x],z = fa[y];
int k = c[y][] == x;
if(!isroot(y)) c[z][c[z][]==y]=x;
fa[x] = z;
c[y][k] = c[x][k^]; fa[c[x][k^]] = y;
c[x][k^] = y; fa[y] = x;
up(y); up(x);
} inline void pushdown(int x){
if(rev[x]){
if(ls) pushrev(ls);
if(rs) pushrev(rs);
rev[x] = ;
}
if(mul[x]!=){
if(ls) pushmul(ls,mul[x]);
if(rs) pushmul(rs,mul[x]);
mul[x] = ;
}
if(add[x]){
if(ls) pushadd(ls,add[x]);
if(rs) pushadd(rs,add[x]);
add[x] = ;
}
} inline void splay(int x){
S[top=]=x;
for(int i = x;!isroot(i);i=fa[i]) S[++top] = fa[i];
while(top) pushdown(S[top--]);
while(!isroot(x)){
int y = fa[x],z = fa[y];
if(!isroot(y))
(c[y][]==x)^(c[z][]==y)?rotate(x):rotate(y);
rotate(x);
}
} inline void access(int x){
for(int y = ;x;y = x,x = fa[x])
splay(x),c[x][] = y,up(x);
} inline void makeroot(int x){
access(x); splay(x); pushrev(x);
} 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); fa[x] = c[y][] = ; up(y);
} inline int findroot(int x){
access(x); splay(x);
while(ls) x = ls;
return x;
} int main()
{
int n,q,u,v,x,y,k;
scanf("%d%d",&n,&q);
for(int i = ;i <= n;i ++) val[i] = mul[i] = ;
for(int i = ;i < n;i ++){
scanf("%d%d",&u,&v);
link(u,v);
}
char op[];
while(q--){
scanf("%s",op);
scanf("%d%d",&u,&v);
if(op[] == '+') {
scanf("%d",&k);
split(u,v); pushadd(v,k);
}
else if(op[] == '-'){
scanf("%d%d",&x,&y);
cut(u,v); link(x,y);
}
else if(op[] == '*'){
scanf("%d",&k);
split(u,v); pushmul(v,k);
}
else if(op[] == '/'){
//cout<<u<<" "<<v<<endl;
split(u,v); printf("%d\n",sum[v]);
}
}
return ;
}