P5227 [AHOI2013] 连通图
（膜拜并感谢 @Genius_Z 给予本题解思路）
因为这一题是线段树合并板题，所以我们使用 LCT。
考虑最暴力的想法，维护一棵树和很多不在树上的边，每一次询问就暴力拆边，从那些没有被禁的边里面补到树上。
这个时候我们就会发现，每次 “补边” 的操作非常的消耗时间。
于是我们就可以想到利用一些 LCT 的性质优化一下。观察题目的本质，其实就是把每一个边按照询问的时间分成很多段 “启用区间” ，那我们 “补边” 的本质又是什么呢？
假设我们断了一条边 a，启用了另一条边 b，那么就说明当前的询问时间 超过了 a 目前的启用区间，而并没有超过 b 的启用区间。那么只要我使树上的边的启用区间右端点尽量的大，是不是就不需要补边了?
考虑对边额外标定一些边权 \(vl_i\)，表示下一次被禁用的询问时间，也就是启用区间的右端点 +1，然后跑最大生成树，每次询问就断边，修改预处理出来的新边权，再加边即可。
至此，我们就还剩下一个问题：我不会维护虚子树的 size。
这其实也非常好解决，只需要在涉及虚实儿子更改的地方（access 操作、link 操作）统计一下虚儿子的 size 之和。当然还有重中之重，为了 cut 操作的方便，我们需要在其中多split一下，确保两个点是实儿子与父亲的关系，不然我们不知道到底是实儿子还是虚儿子。
现在，我们可以用 LCT 切了这道题霸气离场，然后回家偷偷补线段树分治的知识了。
代码 3K，不多
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10,inf=1e9+10;
int tg[N],s[N][2],f[N],st[N],top,n,m,k,vl[N],sz[N],xu[N],a[N],a1,a2;
void up(int x){
sz[x]=sz[s[x][0]]+sz[s[x][1]]+xu[x]+(x<=n);
if(x>n) vl[x]=x;
else vl[x]=0;
if(s[x][0]&&a[vl[s[x][0]]]<a[vl[x]]) vl[x]=vl[s[x][0]];
if(s[x][1]&&a[vl[s[x][1]]]<a[vl[x]]) vl[x]=vl[s[x][1]];
}
void rev(int x){swap(s[x][0],s[x][1]),tg[x]^=1;}
void down(int x){if(tg[x]) rev(s[x][0]),rev(s[x][1]);tg[x]=0;}
int get(int x){return s[f[x]][1]==x;}
int nrt(int x){return s[f[x]][0]==x||s[f[x]][1]==x;}
void rot(int x){
int y=f[x],z=f[y],o=get(x);
if(nrt(y)) s[z][get(y)]=x;
f[x]=z;
s[y][o]=s[x][o^1],f[s[x][o^1]]=y;
s[x][o^1]=y,f[y]=x;
up(y),up(x);
}
void upd(int x){
st[top=1]=x;
while(nrt(x)) st[++top]=x=f[x];
while(top) down(st[top--]);
}
void splay(int x){
upd(x);
for(int y;y=f[x],nrt(x);rot(x)) if(nrt(y)) rot(get(x)^get(y)?x:y);
up(x);
}
void access(int x){for(int y=0;x;x=f[y=x]) splay(x),xu[x]+=sz[s[x][1]],s[x][1]=y,xu[x]-=sz[y],up(x);}
void make(int x){access(x),splay(x),rev(x);}
int find(int x){
access(x),splay(x),down(x);
while(s[x][0]) down(x=s[x][0]);
splay(x);
return x;
}
void split(int x,int y){make(x),access(y),splay(y);}
void link(int x,int y){
make(y);
f[y]=x,xu[x]+=sz[y],up(x);
}
void cut(int x,int y){
split(y,x);
s[x][0]=f[y]=0,up(x);
}
struct node{
int x,y,z,p;
}u,kk[N];
vector<node>d[N];
int nxt[2][N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&u.x,&u.y),u.z=i+n,kk[i]=u;
scanf("%d",&k);
for(int i=1;i<=k;i++){
int oo,uu,v;
scanf("%d",&oo);
for(int j=1;j<=oo;j++){
scanf("%d",&uu),d[i].push_back(kk[uu]),v=kk[uu].z;
if(nxt[0][v]) d[nxt[0][v]][nxt[1][v]].p=i;
else a[v]=i;
nxt[0][v]=i,nxt[1][v]=j-1;
}
}
for(int i=n+1;i<=n+m;i++){
if(nxt[0][i]) d[nxt[0][i]][nxt[1][i]].p=inf;
if(!a[i]) a[i]=inf;
}
for(int i=0;i<=n;i++) a[i]=inf;
for(int i=1;i<=m;i++){
node j=kk[i];
make(j.x);
if(find(j.y)==j.x){
split(j.y,j.x);
int pp=vl[j.x];
if(a[pp]>=a[j.z]) continue;
cut(pp,kk[pp-n].x),cut(pp,kk[pp-n].y);
}
link(j.z,j.x),link(j.z,j.y);
}
for(int i=1;i<=k;i++){
for(node j:d[i]){
make(j.x);
if(find(j.y)==j.x){
up(j.z);
if(!f[j.z]&&!sz[j.z]) continue;
cut(j.z,j.x),cut(j.z,j.y);
}
}
access(1),splay(1);
if(sz[1]==n) puts("Connected");
else puts("Disconnected");
for(node j:d[i]){
make(j.x),a[j.z]=j.p;
if(find(j.y)==j.x){
split(j.y,j.x);
int pp=vl[j.x];
if(a[pp]>=j.p) continue;
cut(pp,kk[pp-n].x),cut(pp,kk[pp-n].y);
}
link(j.z,j.x),link(j.z,j.y);
}
}
}