自动搬运

查看原文

来自洛谷，原作者为

	LiWenX 4587

搬运于2025-08-24 22:59:07，当前版本为作者最后更新于2024-06-03 13:16:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

场上差 $10$ 秒首 A 这个题，无语了。

赛时做法。

这种完全二叉树的问题考虑分治递归处理。

首先考虑在树上随一个点，查询所有点与它的 $\operatorname{lca}$ 可以得到什么。

不难发现可以得到它的所有祖先，设祖先 $u$ 的出现次数 $t_u$，如果我们对这些祖先按照 $t$ 排序，显然就可以把它们在树上的深度固定，我们就确定出了树上的一条链了。

不仅如此，我们还可以知道每一个节点在哪个祖先的子树当中，这样就比较好递归处理了。

唯一的问题是，考虑我们最开始随出来的点 $s$，如果 $s$ 不是叶子节点，它的子树扣掉了这个点，并不是一个完全二叉树了，其实这并不好处理，而随机出 $s$ 为叶子的概率只有 $\dfrac{1}{2}$，如何保证必然可以得到一个叶子呢。

注意到，假如我们最开始随出来的是 $s$，对于枚举的一个 $i$，若 $\operatorname{lca}(s,i)=s$，我们可以通过把 $s$ 变成 $i$，不断的迭代，就必然可以保证 $s$ 成为叶子节点，再套用刚刚的做法就可以过了。

实现的时候可以稍微精细化一点，比如对于 $3$ 个点的完全二叉树，可以查询一次解决（直接一次找出它的根）。

貌似 $n=10$ 的时候，这个做法询问次数固定为 $4480$ 次，有点厉害。

#include<bits/stdc++.h>
using namespace std;
int ask(int x,int y){
	cout<<"? "<<x<<' '<<y<<endl;
	int ret;cin>>ret;
	return ret;
}
int fa[1<<10],siz[1<<10];
bool vis[1<<10];
bool cmp(int x,int y){
	return siz[x]>siz[y];
}
vector<int> nxt[1<<10]; 
int n;
void solve(vector<int> vec,int F){
	if(vec.size()<=2){
		for(int u:vec) fa[u]=F;
		return ;
	}
	if(vec.size()==3){
		int lca=ask(vec[0],vec[1]);
		fa[lca]=F;
		for(int u:vec){
			if(u==lca) continue;
			fa[u]=lca;
		}return ;
	}
	int s=vec[0];
	map<int,bool> ma;
	for(int i=1;i<(int)vec.size();i++){
		int lca=ask(s,vec[i]);
		if(lca==s) s=vec[i];
		fa[vec[i]]=lca;
		siz[lca]++;
		ma[lca]=1;
	}
	vector<int> l;
	for(auto u:ma){
		if(u.first==s) continue;
		l.push_back(u.first);
	}
	sort(l.begin(),l.end(),cmp);
	fa[l[0]]=F;
	for(int i=1;i<(int)l.size();i++){
		fa[l[i]]=l[i-1];
	}fa[s]=l.back();
	for(int u:l) vis[u]=1,nxt[u].clear();vis[s]=1,nxt[s].clear();
	for(int u:vec){
		if(vis[u]) continue;
		nxt[fa[u]].push_back(u);
	}
	for(int u:l){
		solve(nxt[u],u);
	}solve(nxt[s],s);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;n=(1<<n)-1;
	vector<int> vec;
	for(int i=1;i<=n;i++){
		fa[i]=-1;
		vec.push_back(i);
	}
	solve(vec,-1);
	cout<<"! ";
	for(int i=1;i<=n;i++){
		cout<<fa[i]<<" ";
	}
}