题解：CF1061F Lost Root / [SNOW] - 63

· · 题解

幽默题，考察选手注意力。

注意到一棵树有超过一半的点是叶子。

注意到可以 O(n) 得到两个点路径上的所有点。

注意到只要得到树的一个经过根且两端是叶子的路径，其中点一定是根。

考虑直接大力把两个叶子找出来。

第一个点随机在叶子上的概率是 \frac12。

第二个点随机在另一个子树的叶子上的概率是 \frac14。

于是蒙对的概率高达 \frac18，出错的概率高达 \frac78。

如果我们跑 59 次，于是出错的概率是 \left(\frac {7}{8}\right)^{59}\approx 3\times10^{-4}。

等会，这个牛大了！

但是知道路径后并不能知道路径顺序。

考虑直接在路径上面进行一个查找，距离叶子的长度如果恰好符合要求那么就是根了。

这一部分的查找大概需要花费的次数是深度的平方。注意到这个远少于 n 并且上面我们讨论的是 59n，留足了充足的空间。

于是我们就能够写出万分之三概率出错的代码。

写这篇题解的时候突然注意到我的代码写丑了，怎么最后的查找写的询问次数最坏高达 20n，不过能过就好后面忘了。

#include<bits/stdc++.h>
using namespace std;
bool que(int a,int b,int c){
    cout<<"? "<<a<<' '<<b<<' '<<c<<endl;
    string s;
    cin>>s;
    return s=="Yes";
}
int n,k;
vector<int>ask(int u,int v){
    vector<int>ret;
    for(int i=1;i<=n;i++)
    if(que(u,i,v))ret.push_back(i);
    return ret;
}
int main(){
    srand(time(0));
    cin>>n>>k;
    int sum=0,flc=n;
    while(flc){
        sum++;
        flc/=k;
    }
    sum--;
    sum*=2;
    while(1){
        int x=rand()%n+1;
        int y=rand()%n+1;
        if(x==y)continue;
        vector<int>ve=ask(x,y);
        if(ve.size()-1!=sum)continue;
        for(int i=0;i<ve.size();i++){
            if(ve[i]==x||ve[i]==y)continue;
            vector<int>flc=ask(ve[i],x);
            if(flc.size()==sum/2+1){
                cout<<"! "<<ve[i]<<endl;
                return 0;
            }
        }
    }
    return 0;
}
//『三名商人与居住在近郊的两名兽人因发生意外罹难。』

// 他们是这么告诉我的。相信商人们说词的我，从兽人夫妇联想到他们可能有孩子。
// 说不定，孩子们现在还在等待父母回家——一想到这里，我就带著商人上山寻找，然后找到了兽人的家。」