题解 P2542 【[AHOI2005]航线规划】
FlashHu
2018-03-26 20:00:43
太弱了不会树剖，觉得LCT好写一些，就上LCT乱搞，当LCT维护双连通分量的练手题好了
正序删边是不好来维护连通性的，于是就像水管局长那样离线处理，逆序完成操作
显然，每个点可以代表一个双连通分量，查询就是链的长度-1
连接一条边，如果在LCT中还没连通就link，如果连通了，显然这里会出现一个环，然后暴力缩点，可以把当前辅助树的根节点当做集合的标志节点，然后dfs整个辅助树，把链上的其它点的并查集祖先暴力改成这个标志节点，最后再断开标志节点与子树的连接。总的暴力修改次数不会超过$N\log N$次，复杂度是对的
但是点缩完了，那它们的子树不会指空吗？所以，access的时候，要更新$x$为$geth(f[x])$
至于常数，LCT也并不是很慢啊。反正~~有了O2~~还是可以做到很优秀的
代码细节很多，调试真心累TAT
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
#define RG register
#define R RG short
#define I inline void
#define IB inline bool
#define IS inline short
#define G ch=getchar()
#define lc c[x][0]
#define rc c[x][1]
const int N=30009,M=100009;
short f[N],c[N][2],s[N],h[N],a[N],b[N],op[N],ans[M];
bool r[N],vis[M];
struct EDGE{//对边排序，方便查找该边是否被删除
short x,y;
IB operator<(const EDGE a)const{
return x<a.x||(x==a.x&&y<a.y);
}
}e[M];
template<typename T>
I in(RG T&z){
RG char G;
while(ch<'-')G;
z=ch&15;G;
while(ch>'-')z*=10,z+=ch&15,G;
}
IS geth(R x){
if(x==h[x])return x;
return h[x]=geth(h[x]);
}
IB nroot(R x){
return c[f[x]][0]==x||c[f[x]][1]==x;
}
I pushup(R x){
s[x]=s[lc]+s[rc]+1;
}
I pushdown(R x){
if(r[x]){
swap(lc,rc);
r[lc]^=1;r[rc]^=1;r[x]=0;
}
}
I pushall(R x){
if(nroot(x))pushall(f[x]);
pushdown(x);
}
I rotate(R x){
R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y))c[z][c[z][1]==y]=x;f[x]=z;
c[x][!k]=y;f[y]=x;
c[y][k]=w;f[w]=y;
pushup(y);
}
I splay(R x){
pushall(x);
R y;
while(nroot(x)){
if(nroot(y=f[x]))
rotate((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
rotate(x);
}
pushup(x);
}
I access(R x){
for(R y=0;x;y=x,x=f[y]=geth(f[x]))//注意更新
splay(x),rc=y,pushup(x);
}
I makeroot(R x){
access(x);splay(x);
r[x]^=1;
}
IS findroot(R x){
access(x);splay(x);
pushdown(x);
while(lc)pushdown(x=lc);
splay(x);
return x;
}
I split(R x,R y){
makeroot(y);
access(x);splay(x);
}
I del(R x,R y){//函数递归缩点
if(x)h[x]=y,del(lc,y),del(rc,y);
}
I merge(R x,R y){
if(x==y)return;//在一个分量里什么都不用干
makeroot(x);
if(findroot(y)!=x){
f[x]=y;return;//等于link
}
del(rc,x);
rc=0;pushup(x);//缩点，删点
}
int main(){
RG int n,m,i,j;
R x,y;
in(n);in(m);
for(i=1;i<=n;++i)s[i]=1,h[i]=i;
for(i=1;i<=m;++i){
in(x);in(y);
if(x>y)swap(x,y);//强制编号，方便以后查找
e[i]=(EDGE){x,y};
}
sort(e+1,e+m+1);
for(j=1;in(op[j]),op[j]!=131;++j){
in(x);in(y);
if(!op[j]){
if(x>y)swap(x,y);
vis[lower_bound(e+1,e+m+1,(EDGE){x,y})-e]=1;
}//重载完小于号，直接二分找到，再打上删除记号
a[j]=x;b[j]=y;
}
for(i=1;i<=m;++i)
if(!vis[i])merge(geth(e[i].x),geth(e[i].y));
for(i=0,--j;j;--j){
x=geth(a[j]);y=geth(b[j]);
if(op[j])split(x,y),ans[++i]=s[x]-1;
else merge(x,y);
}
while(i)printf("%hd\n",ans[i--]);
return 0;
}
```