自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:07:43，当前版本为作者最后更新于2024-12-28 22:27:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

首先，声称答案为边集对称差的大小。显然这是答案的下界，我们需要构造一种方案使得它成立。

（这种思想的好处在于，整道题直接变成了一道构造题，可以用一些数据结构手段解决，而不是飘忽不定的最优化题）

显然，每次删掉一个不在最终边集里面的边，将树分为两个联通块。由于最终是联通的，所以一定能找到一条未加入的、连接两个联通块的边。

考虑加速该流程。设最终边集的边将图连成若干个联通块，如下图所示（红色的边表示最终边集中的边）

按照深度考虑每个联通块。显然，一定有一条边，一个端点在这个联通块里，另一个端点在这个联通块外。

由于我们是按照深度考虑联通块的，所以每次选择的联通块所在子树内所有节点都在这个联通块里。我们可以在联通块的根处维护所有未被加入的边。断掉联通块的根和其原树上的父亲的连边，并且选择另一条边合并到树上，这相当于合并两个联通块。使用启发式合并即可做到 $O(n \log n)$（我写了个 set，是双 $\log$ 的，但是过了）

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,fa[MAXN],dep[MAXN],ff[MAXN];
set<pair<int,int>> g,t;
vector<int> G[MAXN];
int find(int k) {return (fa[k]==k)?k:(fa[k]=find(fa[k]));}
set<pair<int,int>> st[MAXN];
void merge(set<pair<int,int>> &u,set<pair<int,int>>& v) {
	if(u.size()<v.size()) swap(u,v);
	for(auto pr:v) u.insert(pr);
	v.clear();
	return ;
}
void dfs(int u,int f) {
	dep[u]=dep[f]+1,ff[u]=f;
	for(auto v:G[u]) if(v!=f) {
		if(t.find({min(v,u),max(u,v)})!=t.end()) fa[v]=u;
		else fa[v]=v;
		dfs(v,u);
	}
	return ;
}
vector<pair<pair<int,int>,pair<int,int>>> ans;
struct INFO {int dep,u;};
bool operator <(INFO A,INFO B) {return A.dep<B.dep;}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n-1) {
		int u,v;
		cin>>u>>v,u++,v++;
		G[u].push_back(v),G[v].push_back(u),g.insert({min(u,v),max(u,v)});
	}
	ffor(i,1,n-1) {
		int u,v;
		cin>>u>>v,u++,v++,t.insert({min(u,v),max(u,v)});
	}
	fa[1]=1,dfs(1,0);
	for(auto pr:t) {
		int u=pr.first,v=pr.second;
		if(find(u)!=find(v)) st[find(u)].insert({u,v}),st[find(v)].insert({u,v});	
	}
	priority_queue<INFO> q;
	ffor(i,1,n) if(find(i)==i) q.push({dep[i],i});
	while(!q.empty()) {
		int u=q.top().u,x1=-1,x2=-1;
		if(u==1) break ;
		q.pop();
		while(1) {
			auto pr=*st[u].begin();
			st[u].erase(pr);
			x1=pr.first,x2=pr.second;
			if(find(x1)!=find(x2)) break ;
		}
		if(find(x1)!=u) swap(x1,x2);
		ans.push_back({{ff[u]-1,u-1},{x1-1,x2-1}});
		merge(st[find(x2)],st[find(u)]),fa[u]=find(x2);
	}
	cout<<ans.size()<<'\n';
	for(auto pr:ans) cout<<pr.first.first<<' '<<pr.first.second<<' '<<pr.second.first<<' '<<pr.second.second<<'\n';
	return 0;
}