题解：P11779 [COTS 2012] 宿舍移动 / BUKA

· · 题解

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

考虑递归处理。

每次处理一个子树时，花费子树大小次询问找到其一条链，强制其为左链，将其存储在 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;
}