Time Limit:?30 Sec??Memory Limit:?128 MB
Submit:?2928??Solved:?975
[Submit][Status][Discuss]

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行，每行描述一個操作

Output

　　對于每個/對應的答案輸出一行

Sample Input

3 2
1 2
2 3
* 1 3 4
/ 1 1

Sample Output

4

HINT

數據規模和約定

　　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

題解：

　　四種操作顯然要用動態樹來維護，對于+和*的操作，需要打標記，但是在標記下放的時候需要考慮先放+還是先放*的問題。

　　假設現在樹中有權值為x和權值為y的兩個節點，y是x的父親節點，要對它倆依次進行+a1 *b1 *b2 +a2這四種操作，由于y是x的父親，所以只是對y打上標記，不會下放到x節點。x節點應該的值是：(x+a1)*b1*b2+a2=a1*b1*b2*x+a1*b1*b2+a2，令t1=a1*b1*b2 , t2=a1*b1*b2+a2,則原式可以寫成：t1*x+t2 ， 在這里t1即為乘法標記，t2即為加法標記，下放的方式就是 t1*x+t2的形式，從上面的式子可以看出，對于乘法標記了累計原則就是有加有乘，對于加法標記的原則是只乘不加。由此下放標記

　　其余的就是動態樹的常規操作。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 typedef unsigned int UI; 11 const UI maxn=200000; 12 const UI mod=51061; 13 UI N,Q; 14 UI c[maxn][2],fa[maxn],key[maxn],size[maxn],sum[maxn],add[maxn],mul[maxn],st[maxn]; 15 char s[10]; 16 bool rev[maxn]; 17 bool isroot(UI x){ 18 return x!=c[fa[x]][0]&&x!=c[fa[x]][1]; 19 } 20 void calc(UI x,UI a,UI b){//節點x，進行ax+b操作 21 if(x==0) return; 22 key[x]=((key[x]*a)%mod+b)%mod; 23 sum[x]=((sum[x]*a)%mod+(b*size[x])%mod)%mod; 24 add[x]=((add[x]*a)%mod+b)%mod; 25 mul[x]=(mul[x]*a)%mod; 26 } 27 void pushup(UI x){ 28 size[x]=size[c[x][0]]+size[c[x][1]]+1; 29 sum[x]=(sum[c[x][0]]+sum[c[x][1]]+key[x])%mod; 30 } 31 void pushdown(UI x){ 32 UI l=c[x][0],r=c[x][1]; 33 if(rev[x]==true){ 34 rev[x]^=1; rev[l]^=1; rev[r]^=1; 35 swap(c[x][0],c[x][1]); 36 } 37 UI tmpa=add[x],tmpm=mul[x]; 38 add[x]=0; mul[x]=1; 39 if(tmpa!=0||tmpm!=1){ 40 calc(l,tmpm,tmpa); calc(r,tmpm,tmpa); 41 } 42 } 43 void rotate(UI x){ 44 UI y=fa[x],z=fa[y],l,r; 45 if(x==c[y][0]) l=0;else l=1; r=l^1; 46 if(!isroot(y)){ 47 if(y==c[z][0]) c[z][0]=x; 48 else c[z][1]=x; 49 } 50 fa[x]=z; fa[y]=x; fa[c[x][r]]=y; 51 c[y][l]=c[x][r]; c[x][r]=y; 52 pushup(y); pushup(x); 53 } 54 void splay(UI x){ 55 UI top=0; st[++top]=x; 56 for(UI i=x;!isroot(i);i=fa[i]){ 57 st[++top]=fa[i]; 58 } 59 for(UI i=top;i;i--) pushdown(st[i]); 60 while(!isroot(x)){ 61 UI y=fa[x],z=fa[y]; 62 if(!isroot(y)){ 63 if((x==c[y][0]&&y==c[z][0])||(x==c[y][1]&&y==c[z][1])){ 64 rotate(y),rotate(x); 65 } 66 else rotate(x),rotate(x); 67 } 68 else rotate(x); 69 } 70 } 71 void access(UI x){ 72 UI t=0; 73 while(x){ 74 splay(x); 75 c[x][1]=t; pushup(x); 76 t=x; x=fa[x]; 77 } 78 } 79 void rever(UI x){ 80 access(x); splay(x); rev[x]^=1; 81 } 82 void cut(UI x,UI y){ 83 rever(x); access(y); splay(y); c[y][0]=fa[x]=0; 84 } 85 void link(UI x,UI y){ 86 rever(x); fa[x]=y; splay(x); 87 } 88 int main(){ 89 scanf("%u%u",&N,&Q); 90 for(UI i=1;i<=N;i++) key[i]=sum[i]=size[i]=mul[i]=1; 91 for(UI i=1,u,v;i<=N-1;i++){ 92 scanf("%u%u",&u,&v); 93 link(u,v); 94 } 95 for(UI i=1;i<=Q;i++){ 96 UI u1,v1,u2,v2,cc; 97 scanf("%s",s); 98 if(s[0]=='+'){ 99 scanf("%u%u%u",&u1,&v1,&cc); 100 rever(u1); access(v1); splay(v1); 101 calc(v1,1,cc); 102 } 103 else if(s[0]=='-'){ 104 scanf("%u%u%u%u",&u1,&v1,&u2,&v2); 105 cut(u1,v1); link(u2,v2); 106 } 107 else if(s[0]=='*'){ 108 scanf("%u%u%u",&u1,&v1,&cc); 109 rever(u1); access(v1); splay(v1); 110 calc(v1,cc,0); 111 } 112 else{ 113 scanf("%u%u",&u1,&v1); 114 rever(u1); access(v1); splay(v1); 115 printf("%u\n",sum[v1]); 116 } 117 } 118 return 0; 119 }

?

?

?

轉載于:https://www.cnblogs.com/CXCXCXC/p/5193300.html

總結

以上是生活随笔為你收集整理的bzoj 2631: tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。