被gc巨俠D飛來做這題，好惡心，還不讓人在線LCT?T_T （其實明明就是你忘了強行甩鍋）

xgc：并查集亂搞就能過寫什么LCT

動態維護雙聯通分量

我們離線做......

首先做一次最小生成樹，構出搜索樹

然后沒有用到的邊就拿去暴力合并環，用并查集跳著找

完了

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std;struct node {int x,y,next; }a[810000];int len,last[210000]; void ins(int x,int y) {len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len; } int fa[2][210000]; int findfa(int x,int w) {if(fa[w][x]<0)return x;fa[w][x]=findfa(fa[w][x],w);return fa[w][x]; } int dep[210000]; void dfs(int x) {for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(dep[y]==0)dep[y]=dep[x]+1, fa[0][y]=x, dfs(y);} } int Link(int x,int y) {int fx=findfa(x,1),fy=findfa(y,1);if(fx!=fy){int tot=0; x=fx,y=fy;while(x!=y){if(dep[x]<dep[y])swap(x,y);tot+=fa[1][x];fa[1][x]=findfa(fa[0][x],1);x=fa[1][x];}fa[1][x]+=tot;}return -fa[1][findfa(x,1)]; }struct edge{int x,y;}e[410000]; bool v[410000]; int main() {freopen("a.in","r",stdin);freopen("a.out","w",stdout);int n,m,Q,x,y;scanf("%d%d%d",&n,&m,&Q);for(int i=1;i<=n;i++)fa[1][i]=-1;len=1;memset(last,0,sizeof(last));memset(v,false,sizeof(v));for(int i=1;i<=m+Q;i++){scanf("%d%d",&e[i].x,&e[i].y);int fx=findfa(e[i].x,1),fy=findfa(e[i].y,1);if(fx!=fy){v[i]=true; fa[1][fx]=fy;ins(e[i].x,e[i].y), ins(e[i].y,e[i].x);}}memset(dep,0,sizeof(dep));for(int i=1;i<=n;i++)if(dep[i]==0) dep[i]=1, fa[0][i]=0, dfs(i);for(int i=1;i<=n;i++)fa[1][i]=-1;for(int i=1;i<=m+Q;i++){if(v[i]==true){if(i>m)printf("No\n");}else{int d=Link(e[i].x,e[i].y);if(i>m){if(d==-1)printf("No\n");else printf("%d\n",d);}}}return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/9673385.html

總結

以上是生活随笔為你收集整理的bzoj4998: 星球联盟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。