[AHOI2005]航线规划（边树剖，无向图连通性）

#include <cstdio>
#include <cstdlib>
#include <map>
using namespace std;
const int N=3e4+10,M=2e5+10;
bool used[M],cut[M];
int head[N],to[M],nxt[M],from[M],b_tot=1;//边 
int n,m,a,b,q[M][3],Q,ans[M];//输入
int dfn[N],son[N],si[N],t_tot,top[N],dep[N],fa[N];//树剖 
map <int,int> dict;
struct node
{
    int lc,rc,l,r,sum;
    bool delay;
}f[N*2];
int rt,s_tot;
void dfs1(int u,int fx)
{
    dep[u]=dep[fx]+1;
    fa[u]=fx,si[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(si[v] || cut[i]) continue;
        used[i]=true;
        dfs1(v,u),si[u]+=si[v];
        if(!son[u] || si[son[u]]<si[v]) son[u]=v;
    }
}
void dfs2(int u)
{
    dfn[u]=++t_tot;
    if(son[u]) top[son[u]]=top[u],dfs2(son[u]);
    else return ;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(!used[i] || v==son[u]) continue;
        top[v]=v,dfs2(v);
    }
}
void push_down(int g)
{
    if(!f[g].delay) return ;
    int lc=f[g].lc,rc=f[g].rc;
    f[lc].delay=f[rc].delay=true;
    f[lc].sum=f[rc].sum=0;
    f[g].delay=false;
}
void push_up(int g)
{
    f[g].sum=f[f[g].lc].sum+f[f[g].rc].sum;
}
void build(int &g,int l,int r)
{
    g=++s_tot;
    f[g].l=l,f[g].r=r;
    if(l==r)
    {
        if(l!=1) f[g].sum=1;
        else f[g].sum=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(f[g].lc,l,mid);
    build(f[g].rc,mid+1,r);
    push_up(g);
}
void add(int x,int y)
{
    to[++b_tot]=y,from[b_tot]=x,nxt[b_tot]=head[x],head[x]=b_tot;
    dict[x*n+y]=dict[y*n+x]=b_tot;
    to[++b_tot]=x,from[b_tot]=y,nxt[b_tot]=head[y],head[y]=b_tot;
}
void change(int g,int l,int r)
{
    if(f[g].delay) return;
    if(f[g].l>=l && f[g].r<=r)
    {
        f[g].delay=true,f[g].sum=0;
        return;
    }
    int mid=(f[g].l+f[g].r)>>1;
    if(r<=mid) change(f[g].lc,l,r);
    else if(l>mid) change(f[g].rc,l,r);
    else change(f[g].lc,l,mid),change(f[g].rc,mid+1,r);
    push_up(g);
}
int get(int g,int l,int r)
{
    if(f[g].l>=l && f[g].r<=r) return f[g].sum;
    push_down(g);
    int mid=(f[g].l+f[g].r)>>1;
    if(r<=mid) return get(f[g].lc,l,r);
    else if(l>mid) return get(f[g].rc,l,r);
    else return get(f[g].lc,l,mid)+get(f[g].rc,mid+1,r);
}
int Get(int x,int y)
{
    if(x==y) return 0;
    int ans=0;
    int px=top[x],py=top[y];
    while(px!=py)
        if(dep[px]>=dep[py])
        {
            ans+=get(rt,dfn[px],dfn[x]);
            x=fa[px],px=top[x];
        }
        else
        {
            ans+=get(rt,dfn[py],dfn[y]);
            y=fa[py],py=top[y];
        }
    if(dfn[x]<dfn[y]) ans+=get(rt,dfn[x]+1,dfn[y]);
    if(dfn[y]<dfn[x]) ans+=get(rt,dfn[y]+1,dfn[x]);
    return ans;
}
void Change(int x,int y)
{
    if(x==y) return;
    int px=top[x],py=top[y];
    while(px!=py)
        if(dep[px]>=dep[py])
        {
            change(rt,dfn[px],dfn[x]);
            x=fa[px],px=top[x];
        }
        else
        {
            change(rt,dfn[py],dfn[y]);
            y=fa[py],py=top[y];
        }
    if(dfn[x]<dfn[y]) change(rt,dfn[x]+1,dfn[y]);
    if(dfn[y]<dfn[x]) change(rt,dfn[y]+1,dfn[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        scanf("%d%d",&a,&b),add(a,b);
    while(1)
    {
        scanf("%d",&q[++Q][0]);
        if(q[Q][0]==-1) break;
        scanf("%d%d",&q[Q][1],&q[Q][2]);
        if(q[Q][0]==0)
        {
            int bh=dict[q[Q][1]*n+q[Q][2]];
            cut[bh]=cut[bh^1]=true;
        }
    }
    Q--;
    dfs1(1,0);
    top[1]=1,dfs2(1);
    build(rt,1,t_tot);
    for(int i=2;i<=b_tot;i+=2)
        if(!cut[i] && !used[i] && !used[i^1]) Change(from[i],to[i]);
    for(int i=Q;i;i--)
    {
        if(q[i][0]==0) Change(q[i][1],q[i][2]);
        else ans[++ans[0]]=Get(q[i][1],q[i][2]);
    }
    for(int i=ans[0];i;i--)
        printf("%d\n",ans[i]);
    return 0;
}