题目描述：
现在，我想知道自己是否还有选择。
给定n个点m条边的无向图以及顺序发生的q个事件。
每个事件都属于下面两种之一：
1、删除某一条图上仍存在的边
2、询问是否存在两条边不相交的路径可以从点u出发到点v
输入：
第一行三个整数n,m,q
接下来m行，每行两个整数u,v，表示u和v之间有一条边
接下来q行，每行一个大写字母o和2个整数u、v，依次表示按顺序发生的q个事件：
当o为’Z’时，表示删除一条u和v之间的边
当o为’P’时，表示询问是否存在两条边不相交的路径可以从点u出发到点v
输出：
对于每组询问，如果存在，输出Yes,否则输出No
样例输入：
7 8 7
1 2
1 3
1 4
2 3
3 4
3 7
7 4
5 6
Z 1 4
P 1 3
P 2 4
Z 1 3
P 1 3
Z 6 5
P 5 6
样例输出：
Yes
Yes
No
No
数据规模和约定：
对于20%的数据,max(n,m,q)<=100
对于全部数据，max(n,m,q)<=100000
思路：离线做，用动态树维护连通性，对于已经在同一个连通分块里面的两个点，将这两个点之间的所有点全部缩成一个点，这个点就是最上边的那个，也就是split(x,y)以后的y，然后询问的时候，倒着做，拆边变成加边，对于两个询问点，询问他们是不是在同一个缩的点内，如果是，那么他们就有两条边不相交的路线。
1 #include<algorithm> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 #include<map> 7 struct edge{ 8 int u,v,id; 9 }e[200005],ask[200005]; 10 std::map<int,std::map<int,int> >mp; 11 int n,m,q,ts[500005],tx[500005]; 12 int ch[200005][2],fa[200005],f[200005],st[200005],rev[200005],ans[200005]; 13 int read(){ 14 char ch=getchar();int t=0,ff=1; 15 while (ch<'0'||ch>'9'){if (ch=='-') ff=-1;ch=getchar();} 16 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 17 return t*ff; 18 } 19 int Find(int x){ 20 int top=0,i; 21 if (x==f[x]) return x; 22 for (i=x;f[i]!=i;i=f[i]){ 23 ts[++top]=i; 24 } 25 int key=i; 26 for (int i=top;i>=1;i--) 27 f[ts[i]]=key; 28 return key; 29 } 30 bool isroot(int x){ 31 fa[x]=Find(fa[x]); 32 return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x; 33 } 34 void updata(int x){} 35 void pushdown(int x){ 36 int l=ch[x][0],r=ch[x][1]; 37 if (rev[x]){ 38 rev[x]^=1; 39 rev[l]^=1;rev[r]^=1; 40 std::swap(ch[x][0],ch[x][1]); 41 } 42 } 43 void rotate(int x){ 44 int y=fa[x],z=fa[y],l,r; 45 if (ch[y][0]==x) l=0;else l=1;r=l^1; 46 if (!isroot(y)){ 47 if (ch[z][0]==y) ch[z][0]=x;else ch[z][1]=x; 48 } 49 fa[x]=z;fa[y]=x;fa[ch[x][r]]=y; 50 ch[y][l]=ch[x][r];ch[x][r]=y; 51 updata(y);updata(x); 52 } 53 void splay(int x){ 54 int top=0;st[++top]=x; 55 for (int i=x;!isroot(i);i=fa[i]){ 56 st[++top]=fa[i]; 57 } 58 for (int i=top;i>=1;i--) pushdown(st[i]); 59 while (!isroot(x)){ 60 int y=fa[x],z=fa[y]; 61 if (!isroot(y)){ 62 if (ch[y][0]==x^ch[z][0]==y) rotate(x); 63 else rotate(y); 64 } 65 rotate(x); 66 } 67 } 68 void access(int x){ 69 for (int t=0;x;t=x,fa[x]=Find(fa[x]),x=fa[x]){ 70 splay(x); 71 ch[x][1]=t; 72 updata(x); 73 } 74 } 75 int find(int x){ 76 access(x);splay(x); 77 while (ch[x][0]) x=ch[x][0]; 78 return x; 79 } 80 void makeroot(int x){ 81 access(x);splay(x);rev[x]^=1; 82 } 83 void split(int x,int y){ 84 makeroot(x);access(y);splay(y); 85 } 86 void bfs(int x){ 87 int h=1,t=1;tx[h]=x; 88 for (;h<=t;h++){ 89 if (ch[tx[h]][0]) tx[++t]=ch[tx[h]][0]; 90 if (ch[tx[h]][1]) tx[++t]=ch[tx[h]][1]; 91 } 92 for (int i=1;i<=t;i++){ 93 if (i!=1) fa[tx[i]]=0; 94 f[tx[i]]=x;ch[tx[i]][0]=ch[tx[i]][1]=0; 95 } 96 } 97 void link(int x,int y){ 98 x=Find(x);y=Find(y); 99 if (find(x)!=find(y)){ 100 makeroot(x); 101 fa[x]=y; 102 }else{ 103 split(x,y); 104 bfs(y); 105 } 106 } 107 int main(){ 108 n=read();m=read();q=read(); 109 for (int i=1;i<=n;i++) f[i]=i; 110 for (int i=1;i<=m;i++){ 111 e[i].u=read();e[i].v=read(); 112 if (e[i].u>e[i].v) std::swap(e[i].u,e[i].v); 113 mp[e[i].u][e[i].v]++; 114 } 115 char opt[2]; 116 for (int i=1;i<=q;i++){ 117 scanf("%s",opt+1); 118 if (opt[1]=='Z') ask[i].id=1; 119 else ask[i].id=2; 120 ask[i].u=read();ask[i].v=read(); 121 if (ask[i].u>ask[i].v) std::swap(ask[i].u,ask[i].v); 122 if (ask[i].id==2) continue; 123 if (mp[ask[i].u][ask[i].v]>0) mp[ask[i].u][ask[i].v]--; 124 else ask[i].id=0; 125 } 126 for (int i=1;i<=m;i++) 127 if (mp[e[i].u][e[i].v]>0){ 128 link(e[i].u,e[i].v); 129 } 130 for (int i=q;i>=1;i--) 131 if (ask[i].id==1){ 132 link(ask[i].u,ask[i].v); 133 }else 134 if (ask[i].id==2) 135 { 136 if (Find(ask[i].u)!=Find(ask[i].v)) ans[i]=2; 137 else ans[i]=1; 138 } 139 for (int i=1;i<=q;i++) 140 if (ask[i].id==2){ 141 if (ans[i]==1) puts("Yes"); 142 else puts("No"); 143 } 144 }