bzoj2631（權限題。。。）:鏈接
落咕:鏈接
考察的是LCT維護鏈上信息。
但是這個題不一樣的是又有加法又有乘法。。。（有木有想到落咕的模板——線段樹2qwq）
因為乘法的運算優先度比加法高，所以我們要先做乘法再做加法（證明？去看線段樹2的題解吧），push_down的時候要注意一下。
處理一條路徑的時候，直接split拉出來，然后在根節點進行修改就行了，push_down的時候會把它的標記傳遞下去，也就完成了一條路徑上的加乘操作。
注意計算乘法的時候別忘了*1ll，因為有可能爆int（好吧，作為慣例，一般涉及到乘法再取模操作的時候，中間都要加一個強制類型轉換防止爆int qwqwq）
最后還有一個坑點，數據輸入的時候有乘0的情況，所以我們在push_down的時候判斷有沒有乘法標記不能寫if(t[x].mul>1)，正確寫法應該是if(t[x].mul!=1)。。。。

代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define MAXN 100010 #define mod 51061 using namespace std; int n,m,tot; int s[MAXN]; struct Node{int add,mul,v,rev,son,sum,ff,ch[2];}t[MAXN]; inline void push_up(int x) {t[x].sum=(t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].v)%mod;t[x].son=t[t[x].ch[0]].son+t[t[x].ch[1]].son+1; } inline bool isroot(int x){return t[t[x].ff].ch[0]!=x&&t[t[x].ff].ch[1]!=x;} inline void rotate(int x) {int y=t[x].ff;int z=t[y].ff;int k=t[y].ch[1]==x;if(!isroot(y)) t[z].ch[t[z].ch[1]==y]=x; t[x].ff=z;t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].ff=y;t[x].ch[k^1]=y; t[y].ff=x;push_up(y),push_up(x); } inline void Mul(int x,int k) {t[x].mul=1ll*t[x].mul*k%mod;t[x].add=1ll*t[x].add*k%mod;t[x].v=1ll*t[x].v*k%mod;t[x].sum=1ll*t[x].sum*k%mod; } inline void Add(int x,int k) {t[x].add=(t[x].add+k)%mod;t[x].v=(t[x].v+k)%mod;t[x].sum+=1ll*k*t[x].son%mod,t[x].sum%=mod; } inline void push_down(int x) {if(t[x].rev){if(t[x].ch[0]) t[t[x].ch[0]].rev^=1;if(t[x].ch[1]) t[t[x].ch[1]].rev^=1;swap(t[x].ch[0],t[x].ch[1]);t[x].rev^=1;}if(t[x].mul!=1){if(t[x].ch[0]) Mul(t[x].ch[0],t[x].mul);if(t[x].ch[1]) Mul(t[x].ch[1],t[x].mul);t[x].mul=1;}if(t[x].add){if(t[x].ch[0]) Add(t[x].ch[0],t[x].add);if(t[x].ch[1]) Add(t[x].ch[1],t[x].add);t[x].add=0;} } inline void splay(int x) {s[tot=1]=x;for(int i=x;!isroot(i);i=t[i].ff) s[++tot]=t[i].ff;while(tot) push_down(s[tot--]);while(!isroot(x)){int y=t[x].ff;int z=t[y].ff;if(!isroot(y))((t[y].ch[0]==x)^(t[z].ch[0]==y))?rotate(x):rotate(y);rotate(x);} } inline void access(int x) {for(int y=0;x;y=x,x=t[x].ff)splay(x),t[x].ch[1]=y,push_up(x); } inline void makeroot(int x){access(x);splay(x);t[x].rev^=1;} inline void split(int x,int y){makeroot(x);access(y);splay(y);} inline void cut(int x,int y){split(x,y);t[y].ch[0]=t[x].ff=0;push_up(y);} inline void link(int x,int y){makeroot(x);t[x].ff=y;} inline int findroot(int x) { access(x);splay(x);while(t[x].ch[0]) x=t[x].ch[0];return x; } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifscanf("%d%d",&n,&m);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);link(u,v);}for(int i=1;i<=n;i++) t[i].son=t[i].mul=t[i].v=1;for(int i=1;i<=m;i++){char op;int u,v,c,u2,v2;scanf("%c",&op),scanf("%c",&op);if(op=='+'){scanf("%d%d%d",&u,&v,&c);split(u,v);Add(v,c);}else if(op=='-'){scanf("%d%d%d%d",&u,&v,&u2,&v2);cut(u,v);link(u2,v2);}else if(op=='*'){scanf("%d%d%d",&u,&v,&c);split(u,v);Mul(v,c);}else{scanf("%d%d",&u,&v);split(u,v);printf("%d\n",t[v].sum%mod);}} return 0; }

轉載于:https://www.cnblogs.com/fengxunling/p/10285777.html

總結

以上是生活随笔為你收集整理的[国家集训队] tree Ⅱ的全部內容，希望文章能夠幫你解決所遇到的問題。

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