自动搬运

查看原文

来自洛谷，原作者为

	Ireliaღ 逝去的是刀锋，不变的是意志

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

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

以下是正文

学OI一年半，终于切了第一道交互题。

简述题意

有一棵有标号的树，$n$个点，$1$为根，初始只有$1$已知。你可以调用一个explore(x, y)函数，其中$x$为已知点，$y$为未知点，函数会返回从$x$往$y$走的下一个点。限制你调用explore的次数大约为$n \log n$次，你需要猜出整颗树的结构。

解法

首先我们有一个很显然的暴力思路。

对于每一个未知的点，我们从$1$开始调用explore，一直走到这个点。

由于树的深度最坏是$O(n)$的，所以每找一个新点需要的时间也是$O(n)$，总复杂度是$O(n ^ 2)$。

考虑减小每次达到新点的复杂度，也就是减小“深度”，不难想到可以利用点分治的性质，即点分治深度为$O(\log n)$。

维护已知树的点分树，从点分根节点开始，设当前所在节点为$x$，想找到$y$的位置，令$z=$explore(x, y)，那么我们从$z$往上爬点分父亲，一直爬到$x$，就可以用$O(\log n)$的复杂度知道$z$在$x$的哪个点分子树内。我们跳到这个点分儿子，继续重复前面的操作，一直到找到$y$从哪伸出去就可以了。这样，我们每寻找一个$y$节点，时间复杂度是$O(\log ^ 2 n)$，explore的调用次数是$O(\log n)$。

现在我们的问题是，如何给点分树动态加点。我们每次先默认新加点的点分父亲是原树父亲，从这个点往上爬点分父亲，找到最后一个点分子树大小超过点分父亲点分子树大小$0.7$倍的点$x$，把以$x$的点分父亲为根的点分子树所对应的联通块重新构建点分树即可。（说的好绕

对于这道题，我们需要特别注意一下链的情况，允许的调用次数是$O(n + \log n)$的。对于这种情况，我们把寻找节点的次序random_shuffle一下。令已知链的左端点为$l$，右端点为$r$，目标点为$y$，$z=$explore(l, y)，如果$z$未知，就从$z$向$y$推，反之从$r$向$y$推。这样，把$n$个点全部找出来，期望的“失败”次数是$O(\log n)$的。

代码

#include <bits/stdc++.h>
//#include "rts.h"
#define MAXN _________

using namespace std;
const int MAXN = 1e6 + 5;

int n, a[MAXN], vis[MAXN], fini[MAXN];
int explore(int, int);
// int explore(int x, int y) {}
// int main() {}

void WorkLine() {
	srand(time(0));
	for (int i = 1; i < n; i++) a[i] = i + 1;
	random_shuffle(a + 1, a + n);
    int l = 1, r = 1;
	fini[1] = 1;
	for (int i = 1; i < n; i++) {
		int ter = a[i];
		if (fini[ter]) continue;
		int x = explore(l, ter), now = 0;
		if (fini[x]) now = r, r = ter;
		else fini[x] = 1, now = x, l = ter;
		while (!fini[ter]) now = explore(now, ter), fini[now] = 1;
	}
}

int to[MAXN], nx[MAXN], head[MAXN], ecnt;
int dfa[MAXN], ddep[MAXN], dsiz[MAXN], maxw[MAXN], siz[MAXN];
int nowrt;

void Add(int x, int y) {
	to[++ecnt] = y; nx[ecnt] = head[x]; head[x] = ecnt;
	to[++ecnt] = x; nx[ecnt] = head[y]; head[y] = ecnt;
}

int Find(int u, int fa, int tot) {
	siz[u] = 1;
	maxw[u] = 0;
	int res = 0;
	for (int i = head[u]; i; i = nx[i]) {
		int v = to[i];
		if (vis[v] || v == fa) continue;
		int cen = Find(v, u, tot);
		if (!res || maxw[cen] < maxw[res]) res = cen;
		maxw[u] = max(maxw[u], siz[v]);
		siz[u] += siz[v];
	}
	maxw[u] = max(maxw[u], tot - siz[u]);
	if (!res || maxw[u] < maxw[res]) res = u;
	return res;
}

void Divide(int u, int tot) {
	vis[u] = 1;
	for (int i = head[u]; i; i = nx[i]) {
		int v = to[i];
		if (vis[v]) continue;
		int subs = (siz[v] < siz[u] ? siz[v] : tot - siz[u]);
		int subc = Find(v, u, subs);
		dfa[subc] = u;
		ddep[subc] = ddep[u] + 1;
		dsiz[subc] = subs;
		Divide(subc, subs);
	}
}

void Clear(int u, int fa, int lim) {
	dfa[u] = 0;
	ddep[u] = 0;
	dsiz[u] = 0;
	vis[u] = 0;
	for (int i = head[u]; i; i = nx[i]) {
		int v = to[i];
		if (v == fa || ddep[v] < lim) continue;
		Clear(v, u, lim);
	}
};

void Rebuild(int u) {
	int tot = dsiz[u];
	int fa = dfa[u];
    int depth = ddep[u];
	Clear(u, 0, depth);
	int cen = Find(u, 0, tot);
	if (u == nowrt) nowrt = cen;
	dfa[cen] = fa;
	ddep[cen] = depth;
	dsiz[cen] = tot;
	Divide(cen, tot);
}

void Update(int now) {
	int reb = 0;
	while (dfa[now]) {
		if (1.0 * dsiz[now] > 0.7 * dsiz[dfa[now]]) reb = dfa[now];
		now = dfa[now];
	}
	if (reb) Rebuild(reb);
}

void Reach(int ter) {
	int now = nowrt;
	while (!fini[ter]) {
		int nex = explore(now, ter);
		if (!fini[nex]) {
			Add(now, nex);
			dfa[nex] = now;
			ddep[nex] = ddep[now] + 1;
			vis[nex] = 1;
			fini[nex] = 1;
			dsiz[nex] = 0;
			for (int cur = nex; cur; cur = dfa[cur]) dsiz[cur]++;
			now = nex;
			Update(now);
		} else {
			int son = nex;
			while (dfa[son] != now) son = dfa[son];
			now = son;
		}
	}
}

void Work() {
	srand(time(0));
	for (int i = 1; i < n; i++) a[i] = i + 1;
	random_shuffle(a + 1, a + n);
	fini[1] = 1;
	ddep[1] = 1;
	vis[1] = 1;
	dsiz[1] = 1;
	nowrt = 1;
	for (int i = 1; i < n; i++) {
		int ter = a[i];
		if (fini[ter]) continue;
		Reach(ter);
	}
}

void play(int n, int T, int dataType) {
	::n = n;
	if (dataType == 3) WorkLine();
	else Work();
}