傳送門

題意：維護一棵無權樹和一個路徑集合$S$，支持以下操作：

斷邊連邊

在$S$加入中加入一條路徑

刪除$S$中的一條路徑

詢問是否$S$中的所有路徑都經過了邊$(x,y)$

$n\le 10^5,q\le 3\times 10^5$

給每條加入的路徑隨機賦一個權值并把端點異或上這個權值

這樣如果所有路徑都跨越了$u$的子樹，$u$子樹的異或和就等于所有路徑的異或和

用LCT維護

出錯的可能性是有若干條子樹內或外的路徑異或起來等于$0$，這個概率與路徑條數無關，為$\frac{1}{V}$($V$為隨機的值域)

當在int范圍內隨機時，$3\times 10^5$次詢問都不出錯的概率約為$99.986\%$，可以通過

復雜度$O(n\log n)$

注意link的時候要split（即把$y$變成輔助樹上的真根），因為虛子樹會影響$y$祖先的信息

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cstdlib> #define MAXN 100005 #define MAXM 300005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } inline int Rand(){return (rand()<<15)^rand();} int ch[MAXN][2],fa[MAXN],rv[MAXN],val[MAXN],s[MAXN],si[MAXN]; inline void update(int x){s[x]=val[x]^s[ch[x][0]]^s[ch[x][1]]^si[x];} inline void pushr(int x){swap(ch[x][0],ch[x][1]);rv[x]^=1;} inline void pushdown(int x) {if (rv[x]){if (ch[x][0]) pushr(ch[x][0]);if (ch[x][1]) pushr(ch[x][1]);rv[x]=0; } } inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} inline int get(int x){return ch[fa[x]][1]==x;} inline void rotate(int x) {int y=fa[x],z=fa[y];int l=get(x),r=l^1;int w=ch[x][r];if (!isroot(y)) ch[z][get(y)]=x;ch[x][r]=y,ch[y][l]=w;if (w) fa[w]=y;fa[y]=x,fa[x]=z;update(y),update(x); } int q[MAXN],tp; inline void splay(int x) {q[tp=1]=x;for (int i=x;i;i=fa[i]) q[++tp]=fa[i];for (int i=tp;i>=1;i--) pushdown(q[i]);while (!isroot(x)){int y=fa[x];if (!isroot(y)){if (get(x)==get(y)) rotate(y);else rotate(x);}rotate(x);} } inline void access(int x) {for (int y=0;x;y=x,x=fa[x]){splay(x);si[x]^=s[ch[x][1]];si[x]^=s[ch[x][1]=y];update(x);} } inline void evert(int x){access(x),splay(x),pushr(x);} inline void split(int x,int y){evert(x),access(y),splay(y);} inline void link(int x,int y){split(x,y),fa[x]=y,si[y]^=s[x],update(y);} inline void cut(int x,int y){split(x,y);ch[y][0]=fa[x]=0;update(y);} inline int query(int x,int y){split(x,y);return si[y]^val[y];} inline void modify(int x,int v){access(x),splay(x),val[x]^=v,update(x);} int x[MAXM],y[MAXM],v[MAXM],cur,cnt; int main() {read();int n,m;n=read(),m=read();for (int i=1;i<n;i++){int u,v;u=read(),v=read();link(u,v);}while (m--){int type=read();if (type==1){int x,y,u,v;x=read(),y=read(),u=read(),v=read();cut(x,y),link(u,v);}if (type==2){++cnt;x[cnt]=read(),y[cnt]=read(),v[cnt]=Rand();modify(x[cnt],v[cnt]),modify(y[cnt],v[cnt]);cur^=v[cnt];}if (type==3){int k=read();modify(x[k],v[k]),modify(y[k],v[k]);cur^=v[k];}if (type==4){int x,y;x=read(),y=read();puts(query(x,y)==cur? "YES":"NO");}}return 0; }

總結

以上是生活随笔為你收集整理的【UOJ207】共价大爷游长沙【LCT】【异或】【随机化】的全部內容，希望文章能夠幫你解決所遇到的問題。

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