CF650E Clockwork Bomb（树上构造类问题、并查集）

Description

给出两棵 n 结点的有标号树。
每次操作删去第一棵树的一条边，再加上一条边，需要保证此时还是一棵树。
构造一种操作序列，将第一棵树变成第二棵树，使得操作数最小。
n ≤ $5\times 10^5$

Solution

• 显然，对于第一颗树的边$x\leftrightarrow y$，如果这条边在第二颗树中也存在，那么是不可能更改这条边的。
• 一个朴素的想法是直接遍历第一颗树，如果当前节点和其父亲连的边在第二颗树中没出现，那么更改为连向第二颗树中的父节点。
• 但这样会产生一个问题，如果第二棵树的父节点在第一颗树中变成了子节点，那么这条边也留着，所以不能直接连父节点，否则会出现环
• 考虑把用两棵树之间相同的边连接起来的点缩成一个点，因为两棵树都有的边无需改变，所以我们这样做对题目没什么影响
• 我们称这缩点后的点为大点，可以发现第一棵树除了根大点外每个大点中深度最低的那个小点与父节点之间的边是要被改变的，而他们要改成的边是第二棵树中这个大点中深度最低的点与父节点之间的边，所以我们考虑用并查集来做，每个大点即一个并查集，并查集的根为第二棵树中要改变的点。
• 然后在dfs第一棵树时，如果遇见不在第二棵树中的边，查询当前节点所在并查集中的根，将第一棵树中这个节点和父节点之间的边改成它所在并查集的根与它在第二棵树中父节点之间的边。
• 注意：一颗树中出现环，当且仅当一个点和它父节点连的边更改成和它的子树节点连，所以我们从叶子节点往上更新就可以保证不会在操作过程中出现环，即在dfs时要先处理子节点再处理当前节点。

Code

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=5e5+5;
struct Edge{
	int v,nxt;
}e1[N<<1],e2[N<<1];
int n,head1[N],cnt1,head2[N],cnt2,fa1[N],fa2[N];
int bel[N];
struct Ans{int a,b,c,d;};
vector<Ans> ans;
void add1(int u,int v){
	e1[++cnt1].v=v;e1[cnt1].nxt=head1[u];head1[u]=cnt1;
}
void add2(int u,int v){
	e2[++cnt2].v=v;e2[cnt2].nxt=head2[u];head2[u]=cnt2;
}
void dfs1(int u,int f){
	for(int i=head1[u];i;i=e1[i].nxt){
		int v=e1[i].v;
		if(v==f) continue;
		fa1[v]=u;
		dfs1(v,u);
	}
}
void dfs2(int u,int f){
	for(int i=head2[u];i;i=e2[i].nxt){
		int v=e2[i].v;
		if(v==f) continue;
		fa2[v]=u;
		dfs2(v,u);
	}
}
int find(int x){
	if(bel[x]==x) return x;
	return bel[x]=find(bel[x]);
}
void rebuild(int u){
	for(int i=head1[u];i;i=e1[i].nxt){
		int v=e1[i].v;
		if(v==fa1[u]) continue;
		rebuild(v);
		if(u!=fa2[v]&&v!=fa2[u])
            ans.push_back((Ans){u,v,find(v),fa2[find(v)]});
	}
}
int main(){
	scanf("%d",&n);
	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add1(x,y);add1(y,x);
	}
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add2(x,y);add2(y,x);
	}
	dfs1(1,0);dfs2(1,0);
	bel[1]=1;
	for(int i=2;i<=n;i++)
		bel[i]=(fa1[i]==fa2[i]||fa1[fa2[i]]==i)?fa2[i]:i;
	rebuild(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;
}

参考文章：
https://blog.csdn.net/u014664226/article/details/50901616