自动搬运

查看原文

来自洛谷，原作者为

	ケロシ Blue Archive

搬运于2025-08-24 22:57:58，当前版本为作者最后更新于2025-05-12 12:22:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

来补篇题解 111

首先一种想法就是把 $1$ 作为根，然后每次取距离 $1$ 最远的点 $u$，然后依次访问距离 $u$ 距离最近的点，这样第一个查到的没被取出过的点就是 $u$ 的父亲，可以做到 $3n$ 次询问。

const int N = 3e2 + 5;
int p[N], a[N], vis[N];
void solve(int n, int s) {
	ROF(i, n - 1, 1) {
		int u = query(1, i);
		FOR(j, 1, n) {
			int v = query(u, j);
			if(p[v] == u) continue;
			p[u] = v;
			break;
		}
	}
	FOR(i, 2, n) answer(p[i], i);
}

但是每次会查询一个点的所有邻居，而有用的信息只有其父亲，考虑充分利用信息。

还是将 $1$ 作为根，但是这次每次取距离 $1$ 最近的点 $u$，接下来，当 $u$ 还没有确定其父亲的时候，就依次访问其最近的点，直到找到父亲为止。

这样的话，每次 $u$ 可以查询到邻居 $v$，如果 $v$ 被取出过，那么 $v$ 就是 $u$ 的父亲，反之，可以知道 $u$ 是 $v$ 的父亲。这样每次查询就能知道一对父子关系。

这样就做到了 $2n$ 次询问。

const int N = 3e2 + 5;
int p[N], a[N], vis[N];
void solve(int n, int s) {
	vis[1] = 1;
	FOR(i, 1, n - 1) {
		int u = query(1, i);
		vis[u] = 1;
		int c = 0;
		while(! p[u]) {
			int v = query(u, ++ c);
			if(vis[v]) p[u] = v;
			else p[v] = u;
		}
	}
	FOR(i, 2, n) answer(p[i], i);
}