自动搬运

查看原文

来自洛谷，原作者为

	P2441M 却仍愿/坚信着/世间最美好的一切/正御风漂泊

搬运于2025-08-24 21:15:49，当前版本为作者最后更新于2024-08-15 18:52:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

显然由任意的无向简单图 $S$ 构造出来的图 $T$ 一定是一棵树。注意到一棵 $n$ 个点的树（$n\geqslant 2$）总能找到两个叶子节点 $u_1$ 和 $u_2$，我们考虑保留 $u_1$ 到最后，然后不断删除 $u_2$ 及其连出去的所有边。在删边过程中，我们执行类似拓扑排序的操作，维护点的度数，并将度数被减为 $1$ 的点插入队列中，作为下一个叶子节点。

按照上述构造过程，任意一棵树都可以构造出一棵以 $u_1$ 为根的菊花树。如果 $u_1$ 同样是题目给定的树 $T$ 的叶子节点，那么我们就可以把这棵菊花树继续构造成树 $T$ 了，因为菊花树中除了根以外的节点度数都为 $1$。

我们考虑和构造菊花树类似的过程。首先要在 $T$ 中钦定一个叶子节点作为构造菊花树时的根。将其他叶子节点插入队列中。每次从队列中取出一个点 $v$，显然这个点有唯一连出去的一条边 $(v,v')$，对应到菊花树中，就是选出两个度数相同的点 $v$ 和 $v'$，然后我们删去菊花树中 $v$ 和它连出去的边，同时把 $v'$ 插入队列中。

综上，我们总可以通过 $3$ 次构造得到答案，第一次任意构造出一个树 $T'$，第二次对 $T'$ 构造出菊花树 $J$，第三次对菊花树 $J$ 构造出答案 $T$。

后两次构造有队列的维护，时间复杂度都是 $O(m+n)$ 的，而第一次的随意构造是很大的瓶颈。我选择开一个 map 和一个 set，map 用来维护不同度数对应的节点列表，set 用来将不同的度数按照出现次数降序排序，从而 $O(\log n)$ 的取出两个度数相同的点。似乎第一次构造也可以用队列维护 ~（但我不会）~。整个算法时间复杂度为 $O((m+n)\log n)$，常数较大。

还有一个小细节，我们最开始钦定的菊花树的根 $root$，必须在第一次构造出的树 $T'$ 中以叶子节点的形式出现，后续构造才是合法的。因此第一次构造中，若找到的两个度数相同的点 $u$ 和 $v$ 的其中一个是 $root$，则必须选择将 $root$ 删除，以保证 $T'$ 中 $root$ 的度数为 $1$。

其他细节看代码吧~

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <cstring>

using namespace std;

#define speed_up ios::sync_with_stdio(false); cin.tie(nullptr)
const int MAX_N = 1e5 + 5, MAX_M = 2e5 + 5;

int n, ms, mt, rt;
int cnt[MAX_M];
bitset<MAX_N> st;
queue<int> q;

struct AdjList {
	int tot, head[MAX_N], deg[MAX_N], nxt[MAX_M << 1], to[MAX_M << 1];
	bool v[MAX_N];

	void init() {
		tot = 0;
		memset(head, -1, sizeof(head));
	}

	void insert(int x, int y) {
		++deg[y];
		to[++tot] = y;
		nxt[tot] = head[x];
		head[x] = tot;
	}
} gs, gt, tree;

struct MyPair {
	int deg, c;

	MyPair(int d, int c)
		: deg(d), c(c) {}

	bool operator<(const MyPair &rhs) const { return c > rhs.c; }
};

map<int, set<int>> mp;
set<MyPair> s;

int qread() {
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	int res = 0;
	while (ch >= '0' && ch <= '9') {
		res = ((res << 3) + (res << 1)) + (ch - '0');
		ch = getchar();
	}
	return res; 
}

void add(int d, int off) {
	auto it = s.find({ d, cnt[d] });
	if (it != s.end()) s.erase(it);
	cnt[d] += off;
	s.insert({ d, cnt[d] });
}

int main() {
	speed_up;
	gs.init(); gt.init(); tree.init();
	n = qread(); ms = qread();
	for (int i = 1; i <= ms; ++i) {
		int u, v;
		u = qread(); v = qread();
		gs.insert(u, v); gs.insert(v, u);
	}
	mt = qread();
	for (int i = 1; i <= mt; ++i) {
		int u, v;
		u = qread(); v = qread();
		gt.insert(u, v); gt.insert(v, u);
	}

	cout << "3\n";

	// 1. 定根
	for (int i = 1; i <= n; ++i)
		if (gt.deg[i] == 1) st.set(i, 1);
	for (int i = 1; i <= n; ++i)
		if (st[i]) {
			rt = i;
			break;
		}

	// 2. 乱造一个树 T'
	int u = 0, v = 0;
	for (int i = 1; i <= n; ++i) {
		int d = gs.deg[i];
		if (mp.find(d) == mp.end()) mp[d] = { i };
		else mp[d].insert(i);
		add(d, 1);
	}
	for (int i = 1; i < n; ++i) {
		auto it1 = s.begin();
		int d = it1->deg;
		auto it2 = mp[d].begin();
		u = *it2;
		++it2; v = *it2;

		tree.insert(u, v); tree.insert(v, u);
		if (v == rt) swap(u, v);
		gs.v[u] = true;
		mp[d].erase(u);
		add(gs.deg[u], -1);

		cout << u << ' ' << v << '\n';
		for (int i = gs.head[u]; ~i; i = gs.nxt[i]) {
			int y = gs.to[i];
			if (gs.v[y]) continue;
			mp[gs.deg[y]].erase(y);
			add(gs.deg[y], -1);

			--gs.deg[y];
			if (mp.find(gs.deg[y]) == mp.end()) mp[gs.deg[y]] = { y };
			else mp[gs.deg[y]].insert(y);
			add(gs.deg[y], 1);
		}
	}

	// 3. 构造菊花图
	tree.v[rt] = true;
	for (int i = 1; i <= n; ++i)
		if (tree.deg[i] == 1 && !tree.v[i]) q.emplace(i);
	while (!q.empty()) {
		int v = q.front(); q.pop();
		if (tree.v[v]) continue;
		tree.v[v] = true;
		cout << v << ' ' << rt << '\n';
		for (int i = tree.head[v]; ~i; i = tree.nxt[i]) {
			int y = tree.to[i];
			if (tree.v[y]) continue;
			if (--tree.deg[y] == 1) q.emplace(y);
			break;
		}
	}

	// 4. 构造目标树
	for (int i = 1; i <= n; ++i)
		if (gt.deg[i] == 1 && i != rt) q.emplace(i);
	while (!q.empty()) {
		int v = q.front(); q.pop();
		if (gt.v[v]) continue;
		gt.v[v] = true;
		for (int i = gt.head[v]; ~i; i = gt.nxt[i]) {
			int y = gt.to[i];
			if (gt.v[y]) continue;
			cout << v << ' ' << y << '\n';
			if (--gt.deg[y] == 1) q.emplace(y);
			break;
		}
	}

	return 0;
}