正题

题目链接:https://www.luogu.com.cn/problem/CF650E

---

题目大意

给出$n$个点的两棵树，你每次可以选择第一棵树上的一条边改成另一条边，但是改完之后必须还是一棵树，求最少的步数把第一棵树改成第二棵树。

$1\le n\le 5\times 10^5$

---

解题思路

难点在于不能形成环，所以我们肯定不能随意选择删除边的顺序。

我们指定一号点当根，我们在第一棵树上从下往上删除这样就不会产生环了。

然后我们用并查集把两边已经相同的边的点缩起来，然后枚举所有第一棵树上有且第二棵树上没有的边，断开这条边然后连接一条边，我们可以找到这个缩成点的原来顶部和其父亲连接上。

时间复杂度：$O(n\alpha (n))$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=5e5+10; struct node{int a,b,c,d; }; struct edge{int to,next; }a[N<<1]; int n,tot,fa[N],ls[N],f[N],g[N]; vector<int> T[N]; vector<node> ans; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } int find(int x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} void dfs(int x){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==f[x])continue;f[y]=x;dfs(y);}return; } void dgs(int x){for(int i=0;i<T[x].size();i++){int y=T[x][i];if(y==g[x])continue;g[y]=x;dgs(y);}return; } void solve(int x){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==f[x])continue;solve(y);if(g[y]!=x&&g[x]!=y){ans.push_back((node){x,y,find(y),g[find(y)]});}}return; } int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);T[x].push_back(y);T[y].push_back(x);}dfs(1);dgs(1);fa[1]=1;for(int x=2;x<=n;x++){int y=g[x];if(f[x]==y||f[y]==x)fa[x]=y;else fa[x]=x;}solve(1);printf("%d\n",ans.size());for(int i=0;i<ans.size();i++)printf("%d %d %d %d\n",ans[i].a,ans[i].b,ans[i].c,ans[i].d);return 0; }

总结

以上是生活随笔为你收集整理的CF650E-Clockwork Bomb【并查集】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。