LCT
又一道名字叫做Tree的题目……
看到删边加边什么的……又是动态树问题……果断再次搬出LCT。
这题比起上道【3282】tree的难点在于需要像线段树维护区间那样，进行树上路径的权值修改&查询。那么类似的，我们就可以在splay的每个节点上记录一坨信息了……
个人感觉跟线段树标记不一样的地方：
1.标记只是给儿子们用的，打标记的节点本身在打标记的同时就修改了信息了，然后在Push_down的时候直接放下去……（没法在push_down的时候更新自己，要不mul标记怎么改？）
2.虽然splay是按深度为关键字排序的，但是我们对整条路径操作的时候只要把一个端点上打了标记并且修改了就行了……（当然这个节点必须是“树根”）不用在意顺序……反正都加了就对了= =
虽然不是很明白为什么这样打标记就是对的，在更改树的样子的时候也不会变……但是隐隐地感觉这样是可行的，而且也对了= =就这样姑且记下来好了
另外，学习了另外一位大神的LCT模板，好像会快一些……？
1 /************************************************************** 2 Problem: 2631 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:14720 ms 7 Memory:5724 kb 8 ****************************************************************/ 9 10 //BZOJ 2631 11 #include<cstdio> 12 #include<cstring> 13 #include<cstdlib> 14 #include<iostream> 15 #include<algorithm> 16 #define rep(i,n) for(int i=0;i<n;++i) 17 #define F(i,j,n) for(int i=j;i<=n;++i) 18 #define D(i,j,n) for(int i=j;i>=n;--i) 19 using namespace std; 20 const int N=100086,MOD=51061; 21 //#define debug 22 void read(int &v){ 23 v=0; 24 int sign=1; char ch=getchar(); 25 while(ch<'0' || ch>'9'){ if (ch=='-') sign=-1; ch=getchar();} 26 while(ch>='0' && ch<='9'){v=v*10+ch-'0'; ch=getchar();} 27 v*=sign; 28 } 29 //template of link-cut-tree for NOI2014 magic foreast 30 31 int fa[N],c[N][2],size[N],n,m; 32 unsigned int val[N],mul[N],add[N],sum[N]; 33 bool rev[N]; 34 #define L c[x][0] 35 #define R c[x][1] 36 /* 37 void Push_up(int x){ 38 mid[x]=val[mid[c[x][0]]]>val[mid[c[x][1]]] ? mid[c[x][0]] : mid[c[x][1]] , 39 val[mid[x]]< val[x] ? mid[x]=x : 1; 40 } 41 */ 42 void Push_up(int x){ 43 sum[x]=val[x]; size[x]=1; 44 L ? sum[x]=(sum[x]+sum[L]) % MOD, 45 size[x]+=size[L] : 1; 46 R ? sum[x]=(sum[x]+sum[R]) % MOD, 47 size[x]+=size[R] : 1; 48 } 49 inline void update(int x,int mu,int ad){ 50 val[x]=(val[x]*mu+ad) % MOD; 51 sum[x]=(sum[x]*mu+ad*size[x]) %MOD; 52 mul[x]=(mul[x]*mu) % MOD; 53 add[x]=(add[x]*mu+ad) % MOD; 54 } 55 int swap_tmp=0; 56 void Push_down(int x){ 57 rev[x] ? rev[x]=0,rev[L]^=1,rev[R]^=1,swap_tmp=L,L=R,R=swap_tmp : 1; 58 if(mul[x]!=1 || add[x]!=0) update(L,mul[x],add[x]),update(R,mul[x],add[x]),mul[x]=1,add[x]=0 ; 59 } 60 bool not_root(int x){ 61 return c[fa[x]][0]==x || c[fa[x]][1]==x; 62 } 63 void rotate(int x){ 64 int y=fa[x],p=c[y][1]==x; 65 fa[x]=fa[y], not_root(y) ? c[fa[y]][ c[fa[y]][1]==y ]=x:1, 66 (c[y][p]=c[x][!p]) ? fa[c[y][p]]=y : 1, 67 Push_up(c[ fa[y]=x ][!p]=y); 68 } 69 void preview(int x){ 70 if (not_root(x)) preview(fa[x]); 71 Push_down(x); 72 }//从根到x全部Push_down一遍 73 void splay(int x,int y=0){ 74 for(preview(x);not_root(x);rotate(x)) 75 not_root(y=fa[x]) ? rotate( (c[y][1]==x^c[fa[y]][1]==y ? x : y)),1 : 1; 76 Push_up(x); 77 } 78 void access(int x,int las=0){ 79 for(;x;splay(x),c[x][1]=las,las=x,x=fa[x]); 80 } 81 void makeroot(int x){ 82 access(x),splay(x),rev[x]^=1; 83 } 84 int find(int x){ 85 access(x),splay(x); 86 while(c[x][0]) x=c[x][0]; 87 return x; 88 } 89 void link(int x,int y){ 90 makeroot(x),fa[x]=y; 91 } 92 void cut(int x,int y){ 93 makeroot(x),access(y),splay(y); 94 if (c[y][0]==x) c[y][0]=fa[x]=0; 95 } 96 void update_add(int x,int y,int v){ 97 makeroot(x),access(y),splay(y),add[y]=(add[y]+v)%MOD,val[y]=(val[y]+v)%MOD; 98 } 99 void update_mul(int x,int y,int v){ 100 makeroot(x),access(y),splay(y),mul[y]=(mul[y]*v)%MOD,val[y]=(val[y]*v)%MOD,add[y]=add[y]*v%MOD; 101 } 102 void query(int x,int y){ 103 makeroot(x),access(y),splay(y); 104 printf("%d\n",sum[y]); 105 } 106 /* 107 int query(int x,int y){ 108 return makeroot(x),access(y),splay(y),mid[y]; 109 } 110 */ 111 int main(){ 112 #ifndef ONLINE_JUDGE 113 freopen("input.txt","r",stdin); 114 #endif 115 read(n); read(m); 116 F(i,1,n) add[i]=0,val[i]=mul[i]=sum[i]=size[i]=1; 117 int x,y,v; 118 F(i,2,n){ 119 read(x); read(y); 120 link(x,y); 121 } 122 char cmd[5]; 123 F(i,1,m){ 124 scanf("%s",cmd); 125 read(x),read(y); 126 switch(cmd[0]){ 127 case '+': read(v),update_add(x,y,v);break; 128 case '-': cut(x,y); read(x),read(y); link(x,y);break; 129 case '*': read(v),update_mul(x,y,v); break; 130 case '/': query(x,y);break; 131 } 132 #ifdef debug 133 printf("i=%d\n",i); 134 F(x,1,n) printf("%d %d %d %d %d %d %d\n",fa[x],L,R,sum[x],val[x],mul[x],add[x]); 135 #endif 136 } 137 return 0; 138 }