自动搬运

查看原文

来自洛谷，原作者为

	andychen_2012 **

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

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

以下是正文

我们无需考虑左右儿子的问题，因为我们只需要求出每个节点的父亲。

考虑递归处理。

每次处理一个子树时，花费子树大小次询问找到其一条链，强制其为左链，将其存储在 vector 中，而后按顺序处理每个点的右子树，设询问次数为 $f(n)$，则 $f(n)\le n-1+\sum_{i=1}^{\log n} f(\frac{n}{2^i})$，计算后最大值如下：

f[1]=0
f[3]=2
f[7]=8
f[15]=24
f[31]=64
f[63]=160
f[127]=384
f[255]=896
f[511]=2048
f[1023]=4608
f[2047]=10240
f[4095]=22528
f[8191]=49152

具体而言，应如何寻找到一条链呢？在进入一个子树后，我们先随机一个点 $x$。然后以 $x$ 为一个固定的点询问子树内的其他点，设当前询问为 $\mathrm{lca}(x,y)=z$。若 $z$ 在之前的询问中没有作为 $\mathrm{lca}$ 出现过，那么说明 $z$ 为 $x$ 的祖先，则令链经过它，同时标记 $z$。若 $z=x$，则说明 $y$ 在 $x$ 的子树中，将 $x$ 换到 $y$ 上，否则如果 $y \neq z$，那么说明 $y$ 在 $z$ 的子树中，将 $z$ 的子树大小 $+1$。此时我们可以遍历到子树内的所有点，并计算出我们取出的链上每个点的子树大小的值。按子树大小从大到小排序得到的链，深度从小到大，依次为下一个点的父亲。

代码如下：

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline ll read(){
    ll x=0;
    int f=0,ch=0;
    while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
    while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return f?-x:x;
}
inline void write(ll x,char end='\n'){
    if(x==0){
        putchar('0');
        putchar(end);
        fflush(stdout);
        return;
    }
    if(x<0) putchar('-'),x=-x;
    int ch[40]={0},cnt=0;
    while(x){
        ch[cnt++]=(int)(x%10);
        x/=10;
    }
    while(cnt--) putchar(ch[cnt]+48);
    putchar(end);
    fflush(stdout);
}
inline int ask(int u,int v){
	printf("pitaj %d %d\n",u,v);
	fflush(stdout);
	return read();
}
const int N=1e4+5;
int fa[N],tot;
int to[N],id[N];
vector<int> subsz[N];
inline bool cmp(int x,int y){return subsz[x].size()>subsz[y].size();}
inline void solve(int rt,vector<int> sub){
	int n=sub.size();
	++tot;
	vector<int> anc;
	int now=sub[0];
	for(int i=0;i<n;++i){
		int v=sub[i];
		if(now==v) continue;
		if(to[v]==tot) continue;
		int x=ask(now,v);
		if(to[x]!=tot){
			anc.emplace_back(x);
			to[x]=tot;
			subsz[x].clear();
		}
		if(x==now) now=v;
		else if(x!=v) subsz[x].emplace_back(v);
	}
	sort(anc.begin(),anc.end(),cmp);
	for(auto v:anc){
		fa[rt]=v;
		solve(rt*2+1,subsz[v]);
		rt*=2;
	}
	fa[rt]=now;
}
int main(){
	int n=read();
	if(n==1){
		puts("kraj");
		fflush(stdout);
		puts("1");
		fflush(stdout);
		return 0;
	}
	if(n==3){
		int f=ask(1,2);
		puts("kraj");
		fflush(stdout);
		write(f),write(f),write(f);
		return 0;
	}
	vector<int> sub;
	for(int i=1;i<=n;++i) sub.emplace_back(i);
	solve(1,sub);
	fa[0]=fa[1];
	for(int i=1;i<=n;++i) id[fa[i]]=i;
	puts("kraj");
	fflush(stdout);
	for(int i=1;i<=n;++i) write(fa[id[i]/2]);
    return 0;
}