题单：click here
T1.P2542 [AHOI2005] 航线规划
-
虽然一眼 \(\mathtt{LCT}\)，但没有思考（？）
使用一种简陋的方式获得了 \(\mathtt{50pts}\)。
用树链剖分也可做。 -
首先是逆序处理询问，删边变加边。
纯 \(\mathtt{LCT}\) 是错误的，不能直接把产生环的边权变为 \(0\)，如果直接这么做会导致一种情况：有一条需要后来加的边参与才能产生答案的路径被查到，但由于后来加的边产生了环，然后没加进图里，就会导致错误。
因此我们需要缩点。 -
在 \(\mathtt{LCT}\) 的基础上再加一个并查集，表示每个节点在缩点之后是在哪个节点里面。
每次新加一条边时，判一下这条边的两个端点是否已经被缩在一起了。
如果是，那就不用操作。
如果不是，则还需判一下新加这条边会不会新产生一个环，如果会，就把原来的这一棵树缩成一个点。如果不会产生那就直接按缩点后的点编号加就行。 -
最后整个图肯定是一棵树的形状，查一下两点之间的链的长度，再 \(-1\) 就是答案。
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=1e5+10;
int n,m;
int tot=0;
int fr[N];
struct Q{
int opt,u,v,id;
}q[N>>1];
struct Edge{
int u,v;
bool operator<(const Edge &_)const{
return (u==_.u)?v<_.v:u<_.u;
}
}line[N];
bool cut[N];
map<Edge,int>ind;
struct memr{
int son[2];
int siz,val,fa,sum;
int tg,fl;
#define ls(i) tr[i].son[0]
#define rs(i) tr[i].son[1]
}tr[N];
#define isson(i) (ls(tr[i].fa)==i || rs(tr[i].fa)==i)
#define g(i) (rs(tr[i].fa)==i)
int get(int x){
if(fr[x]==x) return x;
return fr[x]=get(fr[x]);
}
void merge(int x,int y){
fr[get(x)]=get(y);
return ;
}
void pushup(int p){
tr[p].siz=tr[ls(p)].siz+tr[rs(p)].siz+1;
tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum+tr[p].val;
return ;
}
void reverse(int p){
if(!p) return ;
swap(ls(p),rs(p));
tr[p].fl^=1;
return ;
}
void change(int p){
if(!p) return ;
tr[p].val=tr[p].sum=0;
tr[p].tg=-1;
return ;
}
void pushdown(int p){
if(tr[p].fl){
reverse(ls(p));
reverse(rs(p));
tr[p].fl=0;
}
if(tr[p].tg){
change(ls(p));
change(rs(p));
tr[p].tg=0;
}
return ;
}
void rotate(int x){
int y=tr[x].fa;
int z=tr[y].fa,f=g(x);
if(isson(y))
tr[z].son[g(y)]=x;
tr[x].fa=z;
tr[y].son[f]=tr[x].son[f^1];
tr[tr[x].son[f^1]].fa=y;
tr[x].son[f^1]=y;
tr[y].fa=x;
pushup(y),pushup(x);
return ;
}
void update(int p){
if(!p) return ;
update(tr[p].fa);
pushdown(p);
return ;
}
void Splay(int x){
update(x);
for(int i;i=tr[x].fa,isson(x);rotate(x))
if(isson(i))
rotate((g(i)==g(x))?i:x);
pushup(x);
return ;
}
void Access(int x){
for(int i=0;x;i=x,x=tr[i].fa=get(tr[x].fa)){
Splay(x);
rs(x)=i;
pushup(x);
}
return ;
}
void make_root(int x){
Access(x);
Splay(x);
reverse(x);
return ;
}
void split(int x,int y){
make_root(x);
Access(y);
Splay(y);
return ;
}
int Find(int x){
Access(x);
Splay(x);
pushdown(x);
while(ls(x))
x=ls(x),pushdown(x);
Splay(x);
return x;
}
void delet(int x,int gl){
if(!x) return ;
if(x!=gl) fr[x]=gl;
delet(ls(x),gl);
delet(rs(x),gl);
return ;
}
void Link(int x,int y){
if(x==y) return ;
make_root(x);
if(Find(y)!=x){
tr[x].fa=y;
return ;
}
delet(rs(x),x);
pushup(x);
return ;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i)
fr[i]=i;
for(int i=1;i<=m;++i){
line[i].u=read(),line[i].v=read();
if(line[i].u>line[i].v)
swap(line[i].u,line[i].v);
ind[line[i]]=i;
}
while(1){
q[++tot].opt=read();
if(q[tot].opt==-1) break;
q[tot].u=read(),q[tot].v=read();
if(q[tot].u>q[tot].v)
swap(q[tot].u,q[tot].v);
if(q[tot].opt==0){
q[tot].id=ind[(Edge){q[tot].u,q[tot].v}];
cut[q[tot].id]=1;
}
}
--tot;
for(int i=1;i<=m;++i){
if(cut[i]) continue;
int u=get(line[i].u),v=get(line[i].v);
Link(u,v);
}
stack<int>ans;
for(int i=tot;i;--i){
int u=get(q[i].u),v=get(q[i].v);
if(q[i].opt==1){
split(u,v);
ans.push(tr[v].siz-1);
}
else Link(u,v);
}
while(ans.size()){
printf("%d\n",ans.top());
ans.pop();
}
return 0;
}