正題

題目鏈接:https://www.luogu.org/problem/P3690

---

題目大意

$n$個點$m$個操作，要求支持

詢問路徑異或和

連接一條邊(若$x,y$沒聯通)

刪除一條邊

修改一個點的權值

---

解題思路

$LCT$板子題不解釋。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e5+100; int n,m,v[N]; struct Link_Cut_Tree{int w[N],fa[N],son[N][2];bool r[N];#define ls son[x][0]#define rs son[x][1]bool nroot(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}void PushUp(int x){w[x]=w[ls]^w[rs]^v[x];return;}void PushR(int x){swap(ls,rs);r[x]^=1;return;}void PushDown(int x){if(r[x]){if(ls) PushR(ls);if(rs) PushR(rs);r[x]=0;}return;}void Rotate(int x){int y=fa[x],z=fa[y],k=(son[y][1]==x),w=son[x][!k];if(nroot(y)) son[z][son[z][1]==y]=x;son[x][!k]=y;son[y][k]=w;if(w) fa[w]=y;fa[y]=x;fa[x]=z;PushUp(y);return;}void PushHall(int x){if(nroot(x)) PushHall(fa[x]);PushDown(x); return;}void Splay(int x){int y=x,z=0;PushHall(x);while(nroot(x)){y=fa[x];z=fa[y];if(nroot(y))Rotate((son[y][0]==x)^(son[z][0]==y)?x:y);Rotate(x);} PushUp(x);return;}void Access(int x){for(int y=0;x;x=fa[y=x])Splay(x),rs=y,PushUp(x);return;}void MakeRoot(int x){Access(x);Splay(x);PushR(x);return;}int FindRoot(int x){Access(x);Splay(x);while(ls) PushDown(x),x=ls;Splay(x);return x;}void Split(int x,int y){MakeRoot(x);Access(y);Splay(y);return;}void Link(int x,int y){MakeRoot(x);if(FindRoot(y)!=x) fa[x]=y;}void Cut(int x,int y){MakeRoot(x);if(FindRoot(y)==x&&fa[y]==x&&!son[y][0]){fa[y]=son[x][1]=0;PushUp(x);} }#undef ls#undef rs }LCT; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&v[i]);while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==0){LCT.Split(x,y);printf("%d\n",LCT.w[y]);}if(op==1){LCT.Link(x,y);}if(op==2){LCT.Cut(x,y);}if(op==3){LCT.Splay(x);v[x]=y;}} }

總結

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

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