题解：P10553 [ICPC2024 Xi'an I] Guess The Tree

· · 题解

场上差 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]<<" ";
    }
}