题解 nflsoj535 【六校联合训练 省选 #4】nickluo的妹子树

简要题意：

[交互题] 有一个\(2^n-1\)个节点的满二叉树，节点分别被编号为\(1\dots2^n-1\)，但你不知道节点和编号是如何对应的。你可以做\(S\)次询问，每次询问一个点\(u\)，交互库会告诉你所有与\(u\)相邻的点。求根节点的编号。

subtask3 \(n=3,S=3\).

subtask4 \(n=4,S=5\).

其他subtask均满足 \(n\leq 12,S\geq 50\)。

首先，满二叉树上，只有根节点的度数为\(2\)（叶子节点度数为\(1\)，其他节点度数为\(3\)）。利用这个性质，我们得到一个朴素做法：对每个点都询问一次，当某个点度数为\(2\)时就是答案了。需要\(2^n-1\)次询问，可以通过subtask1。

（据说）subtask3,4可以手玩。我考场上只手玩出了subtask3。

考虑其它情况。

我们先从二叉树的任意一个节点出发，dfs出从该节点到两个（不相同的）叶子的路径。注意：因为我们不知道树上的祖先-后代关系，所以这个dfs既可能向上走，也可能向下走，但只要我们不往回走，最终一定能搜索到两个叶子。把到这两个叶子的路径拼接起来，就得到了这两个叶子节点之间的路径。满二叉树有一个很美妙的性质：两个叶子的LCA一定在它们路径的正中间。于是我们就得到了这两个叶子节点的LCA。从这个LCA的父亲出发，继续搜索（不能向LCA这个方向走，可以向另外两条出边中的任意一条走），就能再得到一条从LCA的父亲到一个叶子的路径。把这条路径和前面两条到叶子的路径中的任意一条拼接起来。重复上述过程。每次找到的两个叶子的LCA一定在不断向上，因此最终我们一定能走到根节点。同时，容易发现我们每次搜索到的路径长度单调递增，因此最坏情况下的询问次数为：
\[ 1+2+3+\dots+11=66 \]
考虑两个叶子节点之间的路径。当路径长度\(<15\)（也就是LCA的深度\(>5\)时，注：根节点深度为\(1\)），我们重复上述做法。当路径长度\(\geq15\)（也就是LCA的深度\(\leq5\)时），我们从LCA的父亲开始bfs搜索。注意是使用bfs而不是找叶子用的dfs，因为我们不知道哪条边是父亲，哪条边是儿子，用dfs的话很可能会一头扎进儿子里，就gg了。当使用bfs时，因为我们的起点（LCA的父亲）深度\(\leq4\)，从它出发搜索到根节点至多会搜索\(4\)层，也就是会经过\(2^4-1\)个节点。故此时总询问次数为：
\[ 1+2+3+\dots+8+(2^4-1)=51 \]
考虑在bfs时，如果已经询问了\(2^4-2\)个节点还没有找到答案，则最后剩下的一个节点就一定是答案，我们不用询问了。因此可以把询问次数减少到\(50\)，可以通过本题。

参考代码：

//problem:nflsoj535
#include <bits/stdc++.h>
#include "tree.h"
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fst first
#define scd second

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

/*  ------  by:duyi  ------  */ // dysyn1314
const int MAXN=4095;
bool vis[MAXN+1];
vector<int>v[MAXN+1];
void ask(int x){
    if(vis[x])return;
    vis[x]=1;
    v[x]=query(x);
}
int flag;
vector<int> find_path(int x,int frm){
    vector<int>res;
    ask(x);
    if(v[x].size()==1){res.pb(x);return res;}
    if(v[x].size()==2){flag=x;return res;}
    for(int i=0;i<(int)v[x].size();++i)if(v[x][i]!=frm){
        res=find_path(v[x][i],x);
        if(flag)return res;
        break;
    }
    res.pb(x);
    return res;
}
vector<int> merge(vector<int> v1,vector<int> v2){
    for(int i=v2.size()-1;i>=0;--i)v1.pb(v2[i]);
    assert(v1.size()>=3);
    assert(v1.size()%2==1);
    return v1;
}
vector<int> split(vector<int> v){
    assert(v.size()>=3);
    assert(v.size()%2==1);
    int mid=v.size()/2;
    while(v.size()>mid+1)v.pop_back();
    return v;
}
int xx,yy;
int get_lca(vector<int> v){
    assert(v.size()>=3);
    assert(v.size()%2==1);
    xx=v[v.size()/2-1],yy=v[v.size()/2+1];
    return v[v.size()/2];
}
int solve(int n){
    if(n==1)return 1;
    if(n==3){
        //subtask3
        int x1=1,x2=-1,x3=-1;
        vector<int>v1=query(1);
        vector<int>v2,v3;
        #define s1 (int)v1.size()
        #define s2 (int)v2.size()
        #define s3 (int)v3.size()
        
        if(s1==1)v2=query(x2=v1[0]);
        else v2=query(x2=2);
        
        if(s1==2)return x1;
        if(s2==2)return x2;
        if(s1<s2)swap(x1,x2),swap(v1,v2);
        
        if(s1==3 && s2==1){
            if(x1==v2[0]){
                for(int i=0;i<3;++i)if(v1[i]!=x2){x3=v1[i];break;}
                v3=query(x3);
            }
            else{
                v3=query(x3=v2[0]);
            }
        }
        else{
            for(int i=1;i<=7;++i)if(i!=x1 && i!=x2){x3=i;break;}
            v3=query(x3);
        }
        
        if(s3==2)return x3;
        if(s2<s3)swap(x2,x3),swap(v2,v3);
        if(s1<s3)swap(x1,x3),swap(v1,v3);//sort
        
        if(s1==3 && s2==3){
            for(int i=0;i<3;++i){
                for(int j=0;j<3;++j){
                    if(v1[i]==v2[j])return v1[i];
                }
            }
            assert(0);
        }
        
        if(s1==3 && s2==1 && s3==1){
            assert(v2[0]==x1);
            assert(v3[0]==x1);
            for(int i=0;i<3;++i)if(v1[i]!=x2 && v1[i]!=x3)return v1[i];
            assert(0);
        }
        
        assert(0);
    }
    if(n==4){
        //subtask4
        int N=(1<<n)-1;
        for(int i=1;i<=N;++i)vis[i]=0,v[i].clear();
        queue<pii>q;
        int x=1,tot=6,cnt=0;
        ask(x);cnt++;
        if(v[x].size()==1)ask(x=v[x][0]),cnt++,q.push(mk(x,1));
        else q.push(mk(x,0));
        while(!q.empty()){
            int x=q.front().fst,frm=q.front().scd;
            q.pop();
            if(!vis[x])++cnt;
            if(cnt==tot)return x;
            ask(x);
            if(v[x].size()==2)return x;
            if(v[x].size()==1)continue;
            for(int i=0;i<3;++i)if(v[x][i]!=frm){
                q.push(mk(v[x][i],x));
            }
        }
        assert(0);
    }
    //subtask1
    /*
    int N=(1<<n)-1;
    for(int i=1;i<=N;++i){
        vector<int>v=query(i);
        if(v.size()==2)return i;
    }
    */
    //subtask2
    int N=(1<<n)-1;
    for(int i=1;i<=N;++i)vis[i]=0,v[i].clear();flag=0;
    ask(1);
    if(v[1].size()==2)return 1;
    int x=1;
    if(v[1].size()==1){
        x=v[1][0],ask(x);
        if(v[x].size()==2)return x;
    }
    
    vector<int>p1=find_path(v[x][0],x);if(flag)return flag;
    vector<int>p2=find_path(v[x][1],x);if(flag)return flag;
    p1.push_back(x);
    
    while(true){
        p1=merge(p1,p2);
        if(p1.size()>=15)break;
        p2=split(p1);
        int t=get_lca(p1);
        ask(t);
        if(v[t].size()==2)return t;
        int fa_t=0;
        for(int i=0;i<3;++i)if(v[t][i]!=xx && v[t][i]!=yy){fa_t=v[t][i];break;}
        assert(fa_t);
        if(p2.size()==n-1)return fa_t;
        ask(fa_t);
        if(v[fa_t].size()==2)return fa_t;
        
        for(int i=0;i<3;++i)if(v[fa_t][i]!=t){
            p1=find_path(v[fa_t][i],fa_t);if(flag)return flag;
            break;
        }
        p1.pb(fa_t);
    }
    //subtask5,6,7
    int t=get_lca(p1);
    ask(t);
    if(v[t].size()==2)return t;
    int fa_t=0;
    for(int i=0;i<3;++i)if(v[t][i]!=xx && v[t][i]!=yy){fa_t=v[t][i];break;}
    assert(fa_t);
    queue<pii>q;
    q.push(mk(fa_t,t));
    int tot=(1<<4)-1,cnt=0;
    while(!q.empty()){
        int x=q.front().fst,frm=q.front().scd;
        q.pop();
        ++cnt;
        if(cnt==tot)return x;
        ask(x);
        if(v[x].size()==2)return x;
        if(v[x].size()==1)continue;
        for(int i=0;i<3;++i)if(v[x][i]!=frm){
            q.push(mk(v[x][i],x));
        }
    }
}

题解 nflsoj535 【六校联合训练 省选 #4】nickluo的妹子树

原文：https://www.cnblogs.com/dysyn1314/p/12424840.html