【JZOJ 3875】 星球联盟

星球联盟"/>

【JZOJ 3875】 星球联盟

Description

在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。
但是，组成联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。
为了壮大联盟的队伍，这些星球将建设P条新的太空隧道。这P条新隧道将按顺序依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。
如果这条新的太空隧道连接的两个星球属于同一个联盟，就输出一个整数，表示这两个星球所在联盟的星球数。如果这条新的太空隧道连接的两个星球不属于同一个联盟，就输出”No”（不含引号）。

对于100%的数据有1≤N,M,P≤200000。

Analysis

同一个联盟即形成了环
离线
连边的时候（包括询问）如果形成了环就不连，记录下来，如果是询问显然回答NO
这时会形成森林，我们求出每个点的父节点和深度
然后对于连边中形成了环的边，在树上形成的环所到的最远的点就是两点的lca
于是可以将两个点到lca路径上的点全部用并查集并起来，在并查集里记录集合大小来维护答案

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define efo(i,v) for(int i=last[v];i;i=next[i])
using namespace std;
const int N=400010,M=N*2;
int n,m,p,num,tot,to[M],next[M],last[N],f[N],g[N],sum[N],dep[N];
bool bz[M],vis[M];
struct edge
{int x,y;
}b[N];
void link(int u,int v)
{to[++tot]=v,next[tot]=last[u],last[u]=tot;
}
int getfa(int v)
{if(!f[v]) return v;sum[f[v]]+=sum[v];sum[v]=0;return f[v]=getfa(f[v]);
}
void dfs(int v,int fr,int d)
{vis[v]=1,dep[v]=d,g[v]=fr;efo(i,v){int u=to[i];if(u==fr || vis[u]) continue;dfs(u,v,d+1);}
}
int lca(int u,int v)
{int x=getfa(u),y=getfa(v);while(x!=y){if(dep[x]>dep[y]){f[x]=g[x];getfa(x);x=getfa(g[x]);}else{f[y]=g[y];getfa(y);y=getfa(g[y]);}}return sum[getfa(x)];
}
int main()
{int u,v;scanf("%d %d %d",&n,&m,&p);fo(i,1,m+p){scanf("%d %d",&b[i].x,&b[i].y);u=b[i].x,v=b[i].y;int x=getfa(u),y=getfa(v);if(x==y){bz[i]=1;continue;}link(u,v),link(v,u);f[x]=y;}fo(i,1,n)if(!vis[i]) dfs(i,0,0);fo(i,1,n) f[i]=0,sum[i]=1;fo(i,1,m)if(bz[i]){u=b[i].x,v=b[i].y;lca(u,v);}fo(i,m+1,m+p)if(!bz[i]) printf("No\n");else{u=b[i].x,v=b[i].y;printf("%d\n",lca(u,v));}return 0;
}