自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 23:05:44，当前版本为作者最后更新于2025-06-05 19:06:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

被诈骗了。

首先原来有 $n$ 个点和 $2n - 3$ 条边，而构造出两棵不交的树需要 $2n - 2$ 条边，所以不操作肯定不行。

操作一次后有 $n + 1$ 个点和 $2n$ 条边，边数恰好足够，所以我们思考只操作一次是否可行。

答案是可以。我们可以选一个边上的小三角形进行操作。然后构造可以每次删除度数为 $2$ 的点，其恰好有一条边属于 $T_1$，恰好有一条边属于 $T_2$。直到只剩 $4$ 个点时特殊构造。

可以证明点数 $> 4$ 时一定存在度数为 $2$ 的点。考虑初始的边构成了正 $n$ 边形的一个三角剖分，所以边缘的小三角形对应一个度数为 $2$ 的点。所以删度数为 $2$ 的点等价于删除最外面的小三角形。

时间复杂度 $O(n)$。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

int add_vertex(int, int, int);
void report(vector< array<int, 2> >);

const int maxn = 200100;

int n, deg[maxn];
bool vis[maxn];
vector<int> G[maxn];

void construct_two_trees(int _n, vector<int> _u, vector<int> _v) {
	n = _n;
	for (int i = 0; i < n; ++i) {
		G[i].pb((i + 1) % n);
		G[(i + 1) % n].pb(i);
	}
	for (int i = 0; i < n - 3; ++i) {
		int u = _u[i], v = _v[i];
		G[u].pb(v);
		G[v].pb(u);
	}
	for (int i = 0; i < n; ++i) {
		deg[i] = (int)G[i].size();
	}
	vector< array<int, 2> > A, B;
	for (int u = 0; u < n; ++u) {
		if (deg[u] == 2) {
			int v = (u + n - 1) % n, w = (u + 1) % n;
			add_vertex(u, v, w);
			G[u].pb(n);
			G[n].pb(u);
			G[v].pb(n);
			G[n].pb(v);
			G[w].pb(n);
			G[n].pb(w);
			A.pb(array<int, 2>{u, v});
			A.pb(array<int, 2>{v, w});
			A.pb(array<int, 2>{w, n});
			B.pb(array<int, 2>{u, w});
			B.pb(array<int, 2>{u, n});
			B.pb(array<int, 2>{v, n});
			break;
		}
	}
	queue<int> q;
	for (int i = 0; i < n; ++i) {
		deg[i] = (int)G[i].size();
		if (deg[i] == 2) {
			q.push(i);
		}
	}
	while (q.size()) {
		int u = q.front();
		q.pop();
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		int v = 0, w = 0;
		for (int x : G[u]) {
			if (!vis[x]) {
				(v ? w : v) = x;
				if ((--deg[x]) == 2) {
					q.push(x);
				}
			}
		}
		A.pb(array<int, 2>{u, v});
		B.pb(array<int, 2>{u, w});
	}
	report(A);
	report(B);
}