codeforces gym-101755 I-Guess the Tree 交互题、分治、树的直径

题目

题目链接

题意

n=2h−1，且1≤n≤1023 $n=2^h-1，且1\le n\le 1023$
你可以最多询问 2.5∗logn+12∗n $2.5\ast lo{g}_2^{n+1}\ast n$次，任意两点的距离，让你还原一颗完全二叉树。

题解

第一步、肯定要求整棵树的根节点。

• 由于这是一颗完全二叉树，我们可以求出树的一个直径以及直径上的两个点 f1、f2 $f1、f2$，然后枚举点到 f1、f2 $f1、f2$的距离，当这个点到两点的距离相等的时候，这个点就是根节点。
  所使用询问次数：3n。

第二步、递归求解。

• 计算出所有的点到根节点的距离。询问次数:n
• 找出距离根节点为1的点，就是根节点的两个儿子 c1,c2 $c1,c2$，设置 fa[c1]=fa[c2]=rt $fa[c1]=fa[c2]=rt$
• 将剩下的点分配给左右子树：用c1去遍历所有剩下的点，若距离减小，说明该点属于 c1 $c1$子树，否则属于 c2 $c2$子树，将这个点分配给对应的子树并重新更新距离。询问次数:size(rt的子树)次。
• 重复2～3步骤，直至到叶节点。
• 总的询问次数： logn+12∗n $lo{g}_2^{n+1}\ast n$

代码

#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;
const int maxn = 1024;
int dis[maxn][maxn];
int fa[maxn];
int n,h,root;
int ask(int u,int v){
    if(dis[u][v]) return dis[u][v];
    printf("? %d %d\n",u,v);
    fflush(stdout);
    scanf(" %d",&dis[u][v]);
    return dis[v][u] = dis[u][v];
}
void dfs(int rt,unordered_map<int,int> mp){
    if(!mp.size()) return ;
    int c1 = -1,c2 = -1;
    for(auto p : mp){
        if(p.second == 1){
            if(c1 == -1) c1 = p.first;
            else c2 = p.first;
        }
    }
    unordered_map<int,int> mp1,mp2;
    for(auto p : mp){
        if(p.first == c1 || p.first == c2) continue;
        if(ask(p.first,c1) < p.second)
            mp1[p.first] = p.second-1;
        else
            mp2[p.first] = p.second-1;
    }

    fa[c1] = rt;
    fa[c2] = rt;
    dfs(c1,mp1);
    dfs(c2,mp2);
}
int main(){
    //cout<<ask(1,2)<<endl;
    scanf("%d",&n);
    if(n == 1){
        return 0*puts("! 0");
    }
    int t = n+1;
    while(t) h++,t >>= 1;
    h--;
    int f1 = 1,f2 = 1;
    for(int i = 1;i <= n;++i)
        if(ask(i,1) > ask(f1,1))
            f1 = i;
    for(int i = 1;i <= n;++i)
        if(ask(i,f1) > ask(f2,f1))
            f2 = i;
    for(int i = 1;i <= n;++i){
        if(ask(i,f1) == ask(i,f2)){
            root = i;
            break;
        }
    }
    unordered_map<int,int> mp;
    for(int i = 1;i <= n;++i){
        if(root  == i) continue;
        mp[i] = ask(i,root);
    }
    dfs(root,mp);
    printf("! ");
    for(int i = 1;i <= n;++i){
        printf("%d ",fa[i]);
    }
}