bzoj4998 星球联盟

题意：给出一个无向图，有p条待添加的边 两个点连通的定义为：它们之间有两条互不相交的路径（即环形路径） 对于每一次添加边，若这两个点连通，输出连通块的大小，否则输出$No$ ------------ 连通性显然可以用并查集维护 这里连通的定义是两条路径，所以开两个并查集。 用并查集找环，找到之后在LCT上把它缩成一个点 就是$access$操作与以往不同 ``` inline void access(int x) { for (reg int y=0;x;) { splay(x); rs=y; f[y]=x; y=x; x=find(f[x]); } } ``` 注意x要跳到它父亲节点所在连通块的根节点 完整代码如下： ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define ls ch[x][0] #define rs ch[x][1] #define reg register using namespace std; const int N=2e5+5; int n,m,T,ch[N][2],f[N],fa[N],fh[N],tot[N],ans,stack[N]; bool r[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} int Find(int x){return fh[x]==x?x:fh[x]=Find(fh[x]);} inline bool isroot(int x){return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;} inline int get(int x){return ch[f[x]][1]==x;} inline void rev(int x){swap(ls,rs); r[x]^=1;} inline void pushdown(int x) { if (!r[x]) return; if (ls) rev(ls); if (rs) rev(rs); r[x]=0; } inline void rotate(int x) { int y=f[x],z=f[y],k=get(x),w=ch[x][k^1]; if (!isroot(y)) ch[z][get(y)]=x; ch[x][k^1]=y; ch[y][k]=w; if (w) f[w]=y; f[y]=x; f[x]=z; } inline void splay(int x) { int y=x,z,top=0; stack[++top]=y; while (!isroot(y)) stack[++top]=y=f[y]; while (top) pushdown(stack[top--]); while (!isroot(x)) { y=f[x],z=f[y]; if (!isroot(y)) rotate(get(x)^get(y)?x:y); rotate(x); } } inline void access(int x) { for (reg int y=0;x;) { splay(x); rs=y; f[y]=x; y=x; x=find(f[x]); } } inline void makeroot(int x) { access(x); splay(x); rev(x); } inline void split(int x,int y) { makeroot(x); access(y); splay(y); } inline void link(int x,int y) { makeroot(x); f[x]=y; } void dfs(int x,int pre) { if (!x) return; ans+=tot[x]; if (x!=pre) fa[x]=pre,tot[pre]+=tot[x]; dfs(ls,pre); dfs(rs,pre); } inline void add(int x,int y) { ans=0; if (Find(x)!=Find(y)) fh[fh[x]]=fh[y],link(x,y); else split(x,y),dfs(y,y),ch[y][0]=ch[y][1]=0; } int main() { n=read(),m=read(),T=read(); for (reg int i=1;i<=n;i++) fa[i]=fh[i]=i,tot[i]=1; for (reg int i=1,x,y;i<=m;i++) x=find(read()),y=find(read()),add(x,y); while (T--) { int x=find(read()),y=find(read()); add(x,y); if (!ans) puts("No"); else printf("%d\n",ans); } return 0; } ```