Description

在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。

但是，组成联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。

为了壮大联盟的队伍，这些星球将建设P条新的太空隧道。这P条新隧道将按顺序依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。

Solution

看到这题，第一反应就是tarjan缩环，

首先，我们必须保证初始图的连通性必须和最后图的连通性相同，

显然，一条把两张不连通的边的答案就是0，所以先把询问中的这种边连上，

缩完环以后，出来的就是一颗dfs树，在这上边做LCA，

对于一个询问，先求LCA，要么是连向他的父亲，要么是横插边，每次把新的环缩起来，边统计答案，

每次做完以后LCA并不需要维护，（读者们可以思考一下）

复杂度：O(nlog(n))

Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
using namespace std;
const int N=200500,M=18;
int read(int &n)
{
    char ch=' ';int q=0,w=1;
    for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
    if(ch=='-')w=-1,ch=getchar();
    for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,ans,m1,TI;
int B[4*N][3],A[N],B0=1;
int low[N],dfn[N],za[N];
int sum[N],g[N],si[N];
int z[N];
int G[N][M+1],de[N];
int root[N],sc[N][3];
int FA[N];
void link(int q,int w)
{
    B[++B0][0]=A[q];A[q]=B0,B[B0][1]=w,B[B0][2]=0;
    B[++B0][0]=A[w];A[w]=B0,B[B0][1]=q,B[B0][2]=0;
}
void dfsf(int q,int RT)
{
    g[q]=RT;
    efo(i,q)if(!g[B[i][1]])dfsf(B[i][1],RT);
}
int gf(int q){return (g[q]==q)?q:(g[q]=gf(g[q]));}
int tarjan(int q,int c)
{
    za[++za[0]]=q;dfn[q]=low[q]=c;
    si[q]=0;g[q]=q;
    efo(i,q)if(!B[i^1][2])
    {
        B[i][2]=1;
        if(dfn[B[i][1]]<c)
        {
            low[q]=min(low[q],low[B[i][1]]);
        }else low[q]=min(low[q],tarjan(B[i][1],c+1));
    }
    if(low[q]==dfn[q])
    {
        si[q]=1;
        while(za[za[0]]!=q)
        {
            int w=za[za[0]];
            g[w]=q;si[q]++;za[0]--;
        }
        za[0]--;
    }
    return low[q];
}
void dfs(int q,int c,int fa)
{
    G[q][0]=fa;de[q]=c;
    FA[q]=fa;
    efo(i,q)if(B[i][1]!=fa)dfs(B[i][1],c+1,q);
}
int LCA1(int q,int c)
{
    while(de[q]>c)
    {
        int i=0;
        while(de[G[q][i+1]]>=c&&i<M)i++;
        q=G[q][i];
    }
    return q;
}
int LCA(int q,int w)
{
    q=LCA1(q,de[w]);w=LCA1(w,de[q]);
    while(q!=w)
    {
        int i=0;
        while(G[q][i+1]!=G[w][i+1])i++;
        q=G[q][i];w=G[w][i];
    }
    return q;
}
void UP(int q,int w)
{
    while(q!=w)
    {
        g[gf(q)]=gf(w);
        si[w]+=si[q];
        FA[q]=gf(FA[q]);
        q=FA[q];
    }
}
int main()
{
    int q,w,e;
    read(n),read(m),read(m1);
    fo(i,1,m)read(q),read(w),link(q,w);
    fo(i,1,m1)read(sc[i][0]),read(sc[i][1]);
    fo(i,1,n)if(!g[i])dfsf(i,i);
    fo(i,1,m1)if(gf(sc[i][0])!=gf(sc[i][1]))
    {
        g[gf(sc[i][1])]=gf(sc[i][0]);
        link(sc[i][0],sc[i][1]);sc[i][2]=1;
    }
    fo(i,1,n)if(i==gf(g[i]))root[++root[0]]=i;
    memset(dfn,127,sizeof(dfn));
    memset(low,127,sizeof(low));
    fo(i,1,root[0])tarjan(root[i],1);
    fo(i,1,n)
    {
        int j;
        for(j=A[i];B[j][0];j=B[j][0])B[j][1]=g[B[j][1]];
        if(j&&g[i]!=i)
        {
            B[j][1]=g[B[j][1]];
            B[j][0]=A[g[i]];
            A[g[i]]=A[i];A[i]=0;
        }
    }
    fo(i,1,n)
    {
        TI++;
        while(A[i]&&B[A[i]][1]==i)A[i]=B[A[i]][0];
        int j1=A[i];
        z[i]=z[B[j1][1]]=TI;
        for(int j=B[j1][0];j;j=B[j][0])
            if(z[g[B[j][1]]]==TI)
            {
                B[j1][0]=B[j][0];
            }else z[B[j][1]]=TI,j1=j;
    }
    fo(i,1,root[0])dfs(root[i],1,0);
    fo(j,1,M)fo(i,1,n)if(G[i][0])
        G[i][j]=G[G[i][j-1]][j-1];
    fo(i,1,m1)
    {
        if(sc[i][2]){printf("No\n");continue;}
        q=gf(sc[i][0]),w=gf(sc[i][1]);
        e=LCA(q,w);
        q=gf(q);w=gf(w),e=gf(e);
        if(q==w&&q==e){printf("%d\n",si[q]);continue;}
        ans=0;
        UP(q,e);
        UP(w,e);
        printf("%d\n",si[e]);
    }
    return 0;
}