这个还是比较好理解的.
你考虑如果所有边构成一棵树的话直接用 LCT 模拟一波操作就行.
但是可能会出现环,于是我们就将插入/删除操作按照时间排序,然后依次进行.
那么,我们就要对我们维护的生成树改变一下定义:生成树中的每一条边都是关键边,且要求两点间关键边的最小值最大.
什么边能成为关键边?就是这个边要是在当前时刻被删掉的话这个图就不可能联通.
而一条边在插入时如果两个端点不连通,显然是关键边,而如果联通,则替换掉两点路径中结束时间最早的那个边.
那么新加入的边就成为了关键边,之前那个边就没有用了.
#include <bits/stdc++.h> #define N 50002 #define M 500005 #define inf 1000000000 #define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout) using namespace std; struct Link_Cut_Tree { #define lson t[x].ch[0] #define rson t[x].ch[1] int sta[N+M]; struct Node { int ch[2],f,rev,min,id,val; }t[M+N]; int get(int x) { return t[t[x].f].ch[1]==x; } int isrt(int x) { return !(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x); } void pushup(int x) { t[x].id=x; t[x].min=t[x].val; if(lson&&t[lson].min<t[x].min) { t[x].min=t[lson].min; t[x].id=t[lson].id; } if(rson&&t[rson].min<t[x].min) { t[x].min=t[rson].min; t[x].id=t[rson].id; } } void mark(int x) { if(x) t[x].rev^=1,swap(lson,rson); } void pushdown(int x) { if(x&&t[x].rev) { t[x].rev=0; if(lson) mark(lson); if(rson) mark(rson); } } void rotate(int x) { int old=t[x].f,fold=t[old].f,which=get(x); if(!isrt(old)) t[fold].ch[t[fold].ch[1]==old]=x; t[old].ch[which]=t[x].ch[which^1],t[t[old].ch[which]].f=old; t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold; pushup(old),pushup(x); } void splay(int x) { int u=x,v=0,fa; for(sta[++v]=u;!isrt(u);u=t[u].f) sta[++v]=t[u].f; for(;v;--v) pushdown(sta[v]); for(u=t[u].f;(fa=t[x].f)!=u;rotate(x)) { if(t[fa].f!=u) rotate(get(fa)==get(x)?fa:x); } } void Access(int x) { for(int y=0;x;y=x,x=t[x].f) splay(x),rson=y,pushup(x); } void makeroot(int x) { Access(x),splay(x),mark(x); } void split(int x,int y) { makeroot(x),Access(y),splay(y); } int findroot(int x) { Access(x),splay(x); for(;lson;) x=lson; return x; } void link(int x,int y) { makeroot(x),t[x].f=y; } void cut(int x,int y) { makeroot(x),Access(y),splay(y); t[y].ch[0]=t[x].f=0; pushup(y); } #undef lson #undef rson }lct; int n,m,cnt,is[M],U[M],V[M],vised[M]; map<int,int>lst[N]; struct Edge { int u,v,s,t; Edge(int u=0,int v=0,int s=0,int t=0):u(u),v(v),s(s),t(t){} }e[M]; vector<int>Add[M],Del[M]; void Delete_edge(int id) { if(vised[id]) return; int u=e[id].u; int v=e[id].v; int now=id+n; lct.cut(now, u); lct.cut(now, v); } void Add_edge(int id) { int u=e[id].u; int v=e[id].v; int now=id+n; if(lct.findroot(u)==lct.findroot(v)) { lct.split(u,v); if(lct.t[v].min<e[id].t) { int cur=lct.t[v].id; vised[cur-n]=1; lct.cut(cur, e[cur-n].u); lct.cut(cur, e[cur-n].v); lct.t[now].val=e[id].t; lct.pushup(now); lct.link(u,now); lct.link(v,now); } else vised[id]=1; } else { lct.t[now].val=e[id].t; lct.pushup(now); lct.link(now,u); lct.link(now,v); } } int main() { int i,j; // setIO("input"); scanf("%d%d",&n,&m); for(i=1;i<=m;++i) { int op,u,v,pre; scanf("%d%d%d",&op,&u,&v); if(op==2) is[i]=1,U[i]=u,V[i]=v; else { if(op==0) { e[++cnt]=Edge(u,v,i,m+1); lst[u][v]=lst[v][u]=cnt; Add[i].push_back(cnt); } else { pre=lst[u][v]; e[pre].t=i; Del[i].push_back(pre); lst[u][v]=lst[v][u]=0; } } } for(i=1;i<=n;++i) { lct.t[i].val=inf; lct.pushup(i); } for(i=1;i<=m;++i) { for(j=0;j<Add[i].size();++j) Add_edge(Add[i][j]); for(j=0;j<Del[i].size();++j) Delete_edge(Del[i][j]); if(is[i]) printf("%c ",lct.findroot(U[i])==lct.findroot(V[i])?'Y':'N'); } return 0; }