自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

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

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

以下是正文

有点意思的题。

考虑逐个加点。假设已经维护出来原树的一个连通块，我们现在要加入一个新点，即挂一个叶子到这个连通块上。

考虑边分治去找新点应该挂到哪个点上。每次找到一条边 $(u, v)$ 使得它连接的两棵子树大小最大值最小。设新点为 $x$，询问一次 $(x, u, v)$ 即可知道 $x$ 在 $u$ 子树内还是 $v$ 子树内，扔掉另一棵子树然后继续做直到只剩一个点即可。由于树是二叉树所以对于一个 $x$ 至多问 $O(\log n)$ 次，加入 $n$ 个点总共问 $O(n \log n)$ 次。

问题还剩下如何保证新点一定是连通块的叶子。考虑将所有点按照与 $1$ 的距离从小到大排序，依次加入即可。排序需要 $O(n \log n)$ 次询问。

所以我们就以 $O(n \log n)$ 的询问次数做完了。询问次数实际表现差不多是 $2n \log 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;

const int maxn = 520;

int n, p[maxn];
bool vis[maxn];
pii e[maxn];
vector<int> G[maxn];
map< pair< pair<int, int>, int >, int > mp;

inline int ask(int a, int b, int c) {
	if (mp.find(mkp(mkp(a, b), c)) != mp.end()) {
		return mp[mkp(mkp(a, b), c)];
	}
	printf("? %d %d %d\n", a, b, c);
	fflush(stdout);
	int x;
	scanf("%d", &x);
	return mp[mkp(mkp(a, b), c)] = x;
}

int sz[maxn], fa[maxn];

void dfs(int u, int t) {
	sz[u] = 1;
	fa[u] = t;
	for (int v : G[u]) {
		if (v == t || !vis[v]) {
			continue;
		}
		dfs(v, u);
		sz[u] += sz[v];
	}
}

void dfs2(int u, int fa) {
	vis[u] = 0;
	for (int v : G[u]) {
		if (v == fa || !vis[v]) {
			continue;
		}
		dfs2(v, u);
	}
}

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		p[i] = i;
	}
	stable_sort(p + 2, p + n + 1, [&](const int &x, const int &y) {
		return ask(1, x, y) == 1;
	});
	G[1].pb(p[2]);
	G[p[2]].pb(1);
	e[1] = mkp(1, p[2]);
	for (int i = 3; i <= n; ++i) {
		mems(vis, 0);
		for (int j = 1; j < i; ++j) {
			vis[p[j]] = 1;
		}
		while (1) {
			int cnt = 0, u = 0;
			for (int j = 1; j < i; ++j) {
				if (vis[p[j]]) {
					++cnt;
					u = p[j];
				}
			}
			if (cnt == 1) {
				e[i - 1] = mkp(u, p[i]);
				G[u].pb(p[i]);
				G[p[i]].pb(u);
				break;
			}
			dfs(u, -1);
			int mn = 1e9, w = -1;
			for (int j = 1; j < i; ++j) {
				int v = p[j];
				if (u != v && vis[v] && max(sz[v], cnt - sz[v]) < mn) {
					mn = max(sz[v], cnt - sz[v]);
					w = v;
				}
			}
			if (ask(p[i], w, fa[w]) == 1) {
				dfs2(fa[w], w);
			} else {
				dfs2(w, fa[w]);
			}
		}
	}
	puts("!");
	for (int i = 1; i < n; ++i) {
		printf("%d %d\n", e[i].fst, e[i].scd);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}