题解：P11354 [eJOI2023] Tree Search

Lele_Programmer · 2024-12-15 18:47:13 · 题解

P11354 题解

交互题好玩。

思路

询问次数最多为 35，不难想到二分。

也就是说，每一次询问，都要砍掉半棵树。

对于一棵树，由根节点出发，往更大的子树走，直到子树大小不超过原来一整棵树的大小的 \frac{1}{2}，返回该节点。这样一来，在子树大小大于整棵树大小的 \frac{1}{2} 时，会不断地缩小子树大小，逼近总大小的 \frac{1}{2}。

考虑最坏情况，当某棵子树大小为总大小的 \frac{1}{2} 多一个点时，若它的子树大小平分，那么每一次最少会砍掉 \frac{1}{4} 的大小。

由此可得平均询问次数为 \mathcal{O}(\log_2 n)，最坏询问次数为 \mathcal{O}(\log_{\frac{4}{3}} n)，最坏会询问到 40 次。可是呢，感觉造不出这样的数据，因为每次操作都会对整棵树的大小发生变化。能过就行了吧。

代码

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define FRR(file) freopen(file,"r",stdin)
#define FRW(file) freopen(file,"w",stdout)
#define TIMESTAMP cerr<<fixed<<setprecision(3)<<clock()*1.0/CLOCKS_PER_SEC<<"s"<<endl;
#define _rep(i,a,b) for (int i=(a);i<=(b);++i)
#define _reps(i,a,b,c) for (int i=(a);i<=(b);c)
#define _rrep(i,a,b) for (int i=(a);i>=(b);--i)
#define _rreps(i,a,b,c) for (int i=(a);i>=(b);c)
#define _iter(i,a) for (auto i=a.begin();i!=a.end();++i)
#define _graph(i,u) for (int i=h[u];~i;i=ne[i])
#define rint register int
#define LL long long
typedef pair<int,int> pii;

const int N=100005;

int n,root;
int sz[N];
bool flag[N];
vector<int> vec[N];

extern "C" bool ask(int k);

inline void dfs(int u) {
    if (flag[u]) {
        sz[u]=0;
        return;
    }
    sz[u]=1;
    _iter(it,vec[u]) {
        dfs(*it);
        sz[u]+=sz[*it];
    }
}

inline int find(int u) {
    if (sz[u]<=sz[root]/2) return u;
    assert(!vec[u].empty());
    if (vec[u].size()==2 && sz[vec[u][0]]<sz[vec[u][1]]) swap(vec[u][0],vec[u][1]);
    return find(vec[u][0]);
}

extern "C" int solve(int n,vector<int> p) {
    // assert(ask(1)==1);
    _rep(i,0,(int)p.size()-1) vec[p[i]].emplace_back(i+2);
    root=1;
    while (true) {
        dfs(root);
        if (sz[root]==1) return root;
        int t=find(root);
        int k=ask(t);
        if (k) root=t;
        else flag[t]=true;
    }
    return 114514;
}