题解：CF1284F

知道 Hall 定理应该好想。首先要想到对于任意一个 T1 的边集

E

，删去它的边后会得到

|E|+1

个联通块，若把他们放到 T2 上的话，由于 T2 是棵树，所以各点集间仍是联通的，所以至少各点集之间至少有

|E|

个边。由霍尔定理，知一定存在

n-1

条边的完美匹配。

另附霍尔定理的证明：证明

然后如何构造呢？

在用霍尔定理证明时，可能会画出这样的图。

可以描述进行一些匹配后图的形态。其中围在一起的是已经 T1 匹配过的边，其他是未匹配的边。虚线边是 T2 上未匹配的边。容易观察并想到，匹配过的边形成的联通块内没有虚边，联通块间也没有重边。并且剩余实边和虚边数目相当，他们分别构成一棵树。实际上，可以发现这是一个原问题的子问题。所以考虑一边维护问题的性质一边匹配。

虚边和实边匹配，当且仅当实边是该虚边两端点 T1 上的路径的边，并且没被匹配过。又要求 T2 保持树的性质，所以在这虚边匹配后被删去，T2 被分割成两份，匹配的实边将两端的联通块合并后满足性质，需满足两端分属两份。故考虑在 T2 上 dfs，回溯前的（叶）子节点（连通块）一定和所有其他节点（连通块）分属两份，故直接在 T1 的路径上找第一个子连通块向外连的边就可以，可以并查集+倍增维护。

CPP

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> vec1[250002], vec2[250002];
int fa[22][250002], dep[250002], belong[250002];
int owner(int pos){return belong[pos]==pos?pos:belong[pos]=owner(belong[pos]);}
void dfsforfa(int pos,int f){
	dep[pos] = dep[f] + 1;
	fa[0][pos] = f;
	for(int i=0;i<vec1[pos].size();i++){
		int v = vec1[pos][i];
		if(v == f) continue;
		dfsforfa(v, pos);
	}
}
int lca(int u,int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int k=20;k>=0;k--) if(dep[fa[k][u]] >= dep[v]) u = fa[k][u];
	if(u == v) return u;
	for(int k=20;k>=0;k--) if(fa[k][u] != fa[k][v]) u = fa[k][u], v = fa[k][v];
	return fa[0][u];
}

pair<int,int> ans1[250002], ans2[250002];
int anstot;
void solve(int pos,int f){
	for(int i=0;i<vec2[pos].size();i++){
		int v = vec2[pos][i];
		if(v == f) continue;
		solve(v, pos);
	}
	for(int i=0;i<vec2[pos].size();i++){
		int v = vec2[pos][i];
		if(v == f) continue;
		ans2[++anstot] = make_pair(pos, v);
		int LCA = lca(pos, v);
		int pp = pos, tar = owner(v);
		for(int k=20;k>=0;k--) if(dep[fa[k][pp]] >= dep[LCA] && owner(fa[k][pp]) != tar) pp = fa[k][pp];
		if(pp == LCA){
			int vv = v;
			for(int k=20;k>=0;k--) if(dep[fa[k][vv]] >= dep[LCA] && owner(fa[k][vv]) == owner(vv)) vv = fa[k][vv];
			belong[owner(vv)] = owner(fa[0][vv]);
			ans1[anstot] = make_pair(vv, fa[0][vv]);
		}
		else {
			belong[owner(pp)] = owner(fa[0][pp]);
			ans1[anstot] = make_pair(pp, fa[0][pp]);
		}
	}
}

int main(){
	
	cin >> n;
	for(int i=1;i<n;i++){
		int u, v;
		cin >> u >> v;
		vec1[u].push_back(v);
		vec1[v].push_back(u);
	}
	for(int i=1;i<n;i++){
		int u, v;
		cin >> u >> v;
		vec2[u].push_back(v);
		vec2[v].push_back(u);
	}
	cout << n-1 << endl;
	dfsforfa(1, 0);
	for(int i=1;i<=20;i++) for(int j=1;j<=n;j++) fa[i][j] = fa[i-1][fa[i-1][j]];
	for(int i=1;i<=n;i++) belong[i] = i;
	
	solve(1, 0);
	
	for(int i=1;i<=n-1;i++) cout << ans1[i].first << ' ' << ans1[i].second << ' ' << ans2[i].first << ' ' << ans2[i].second << endl;
	
	return 0;
}

自己没想到主要是因为不知道怎么进行子问题的转移吧。重点要想到同时维护 T2 树的性质转化为子问题，以保证最大匹配数不变。

文章操作

相关推荐

评论

题解：CF1284F