題目鏈接：點擊查看

題目大意：給出 n 個帶權節(jié)點，需要執(zhí)行 m 次操作，每次操作分為四種類型：

0 x y?代表詢問從?x?到?y?的路徑上的點的權值的?xor?和。保證?x?到?y?是聯(lián)通的。

1 x y?代表連接?x?到?y，若?x?到?y?已經(jīng)聯(lián)通則無需連接。

2 x y?代表刪除邊?(x,y)，不保證邊?(x,y) 存在。

3 x y?代表將點?x?上的權值變成?y。

題目分析：直接調用相應的函數(shù)即可

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e5+100;int val[N];struct LCT {int fa[N],ch[N][2],sum[N],rev[N],Stack[N],top;bool son(int x)//判斷點x是父節(jié)點的左兒子還是右兒子 {return x==ch[fa[x]][1];}bool isroot(int x)//判斷一個點是不是根節(jié)點（當前splay的根節(jié)點）{return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}void pushup(int x)//上傳(維護信息){sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^val[x];}void reverse(int x)//交換左右子樹 {if(!x)return;swap(ch[x][0],ch[x][1]);rev[x]^=1;}void pushdown(int x)//下傳(更新反轉標記用){if(!rev[x])return;reverse(ch[x][0]);reverse(ch[x][1]);rev[x]=0;}void rotate(int x)//splay的旋轉 {int y=fa[x],z=fa[y],c=son(x);ch[y][c]=ch[x][c^1];if(ch[y][c]) fa[ch[y][c]]=y;fa[x]=z;if(!isroot(y))ch[z][son(y)]=x;ch[x][c^1]=y;fa[y]=x;pushup(y);}void splay(int x)//將x轉到根節(jié)點 {Stack[top=1]=x;for (int i=x;!isroot(i);i=fa[i])Stack[++top]=fa[i];while (top) pushdown(Stack[top--]);for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])if (!isroot(y)) son(x)^son(y)?rotate(x):rotate(y);pushup(x);}void access(int x)//把x節(jié)點到x所在樹（連通塊）的根節(jié)點之間的路徑全部變成重路徑{for (int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pushup(x);}void makeroot(int x)//把x節(jié)點設為x所在樹（連通塊）的根節(jié)點{access(x);splay(x);reverse(x);}int findroot(int x)//找到x節(jié)點所在樹（連通塊）的根節(jié)點{access(x);splay(x);while (ch[x][0]) x=ch[x][0];splay(x);return x;}void split(int x,int y)//摳出x到y(tǒng)的路徑，摳完以后y是splay的根{makeroot(x);access(y);splay(y);}void cut(int x,int y)//砍斷x到y(tǒng)的邊{makeroot(x);if(findroot(y)==x&&fa[y]==x&&!ch[y][0])fa[y]=ch[x][1]=0,pushup(x);}void link(int x,int y)//連接x到y(tǒng)的邊{makeroot(x);if(findroot(y)!=x)fa[x]=y;} }t;int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",val+i);while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==0){t.split(x,y);printf("%d\n",t.sum[y]);}else if(op==1){t.link(x,y);}else if(op==2){t.cut(x,y);}else if(op==3){t.splay(x);val[x]=y;}}return 0; }

?

總結

以上是生活随笔為你收集整理的洛谷 - P3690 【模板】Link Cut Tree （动态树）(LCT模板)的全部內容，希望文章能夠幫你解決所遇到的問題。

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