题目描述
一棵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
题解
一起膜拜flashhu大佬%%%
不知道为什么我的LCT板子好像各种有问题……和大佬的各种操作兼容不起来……然后也不知道要怎么改……
总之就是在树上打上各种标记，然后向线段树一样记得下传……
然后各种细节我一个都没考虑到……多亏了大佬的提醒orz
1 //minamoto 2 #include<bits/stdc++.h> 3 #define int unsigned int 4 #define mod 51061 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 const int N=100005; 19 int n,fa[N],ch[N][2],v[N],sum[N],sz[N],tmul[N],tadd[N],s[N],top,rev[N]; 20 bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} 21 void pushup(int x){ 22 sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+v[x])%mod; 23 sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; 24 } 25 void pushrev(int x){ 26 swap(ch[x][0],ch[x][1]);rev[x]^=1; 27 } 28 #define mul(x) x*=c,x%=mod 29 #define add(x,c) x+=c,x%=mod 30 void pushmul(int x,int c){ 31 mul(sum[x]),mul(v[x]),mul(tmul[x]),mul(tadd[x]); 32 } 33 void pushadd(int x,int c){ 34 add(sum[x],c*sz[x]),add(v[x],c),add(tadd[x],c); 35 } 36 #undef mul 37 #undef add 38 void pushdown(int x){ 39 if(tmul[x]!=1) pushmul(ch[x][0],tmul[x]),pushmul(ch[x][1],tmul[x]),tmul[x]=1; 40 if(tadd[x]) pushadd(ch[x][0],tadd[x]),pushadd(ch[x][1],tadd[x]),tadd[x]=0; 41 if(rev[x]) {if(ch[x][0]) pushrev(ch[x][0]);if(ch[x][1]) pushrev(ch[x][1]);rev[x]=0;} 42 } 43 void rotate(int x){ 44 int y=fa[x],z=fa[y],d=(ch[y][1]==x);if(!isroot(y)) ch[z][ch[z][1]==y]=x; 45 fa[x]=z,fa[y]=x;fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y;pushup(y),pushup(x); 46 } 47 void splay(int x){ 48 s[top=1]=x;for(int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i];for(int i=top;i>=1;--i) pushdown(s[i]); 49 for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){ 50 if(!isroot(y)) ((ch[z][1]==y)^(ch[y][1]==x))?rotate(x):rotate(y);rotate(x); 51 } 52 } 53 void access(int x){int t=0;while(x){splay(x),ch[x][1]=t,pushup(x),t=x,x=fa[x];}} 54 void makeroot(int x){access(x),splay(x),pushrev(x);} 55 int findroot(int x){access(x);splay(x);pushdown(x);while(ch[x][0]) pushdown(x=ch[x][0]);return x;} 56 void split(int x,int y){makeroot(x),access(y),splay(y);} 57 void link(int x,int y){makeroot(x),fa[x]=y;} 58 void cut(int x,int y){split(x,y),fa[x]=ch[y][0]=0;} 59 #undef int 60 int main(){ 61 //freopen("testdata.in","r",stdin); 62 int n,q; 63 n=read(),q=read(); 64 for(int i=1;i<=n;++i) tmul[i]=sz[i]=v[i]=1; 65 for(int i=1;i<n;++i){ 66 int u=read(),v=read(); 67 link(u,v); 68 } 69 while(q--){ 70 char ch; 71 while((ch=getc())<'*'); 72 switch(ch){ 73 case '+':{ 74 int a=read(),b=read(),k=read(); 75 split(a,b),pushadd(b,k); 76 break; 77 } 78 case '-':{ 79 int a=read(),b=read();cut(a,b); 80 a=read(),b=read(),link(a,b); 81 break; 82 } 83 case '*':{ 84 int a=read(),b=read(),k=read(); 85 split(a,b),pushmul(b,k); 86 break; 87 } 88 case '/':{ 89 int a=read(),b=read(); 90 split(a,b); 91 printf("%d ",sum[b]); 92 break; 93 } 94 } 95 } 96 }