A

ImmatureDreamer · 2026-07-19 18:42:04 · 题解

首先通过二分询问 \log n 次，确定 X 的层数。

接下来，考虑每次排除一些 X 可能取的点。思考每次询问树的重心，将树分为几个部分，并确定其在哪些部分。由于是二叉树，去除重心后，每次最多有三个连通块。设最大连通块大小为 siz，则有 \frac{n}{3} \le siz \le \frac{n}{2}。

:::align{center} :::

对每次询问，若最大的连通块在其父亲方向，则至少排除 \frac{n}{2} 个点；若在儿子方向，则至少排除 \frac{n}{3} 个点。对未排除部分继续求重心，最终确定 X 的位置。

这样，就在至多 \log_2 n + \log_\frac{3}{2} n 次询问内求出了答案，对 40 次足够。

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

const int N = 3e4 + 5;

int n, dep[N], root, tot_size, siz[N], xd, mn, p;
bool vis[N];
vector<int> G[N];

int ask(int u, int k){
    cout << "? " << u << " " << k << endl;
    int x;
    cin >> x;
    return x;
}

void dfs(int u){
    siz[u] = 1;
    for(int v : G[u])
        if(!vis[v]){
            dfs(v);
            siz[u] += siz[v];
        }
    if(dep[u] <= xd && max(siz[u], tot_size - siz[u]) < mn)
        mn = max(siz[u], tot_size - siz[u]), p = u;
}

void solve(){
    cin >> n;
    root = 1, tot_size = n;

    for(int i = 1; i <= n; ++ i)
        vis[i] = 0, G[i].clear();

    int max_dep = 0;
    for(int i = 2; i <= n; ++ i){
        int f;
        cin >> f;
        G[f].push_back(i);
        dep[i] = dep[f] + 1;
        max_dep = max(max_dep, dep[i]);
    }

    int l = 0, r = max_dep;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(ask(1, mid)) r = mid - 1, xd = mid;
        else l = mid + 1;
    }

    while(1){
        mn = n + 1;
        dfs(root);
        if(ask(p, xd - dep[p])){
            root = p;
            tot_size = siz[p];
            if(dep[p] == xd)
                break;
        }
        else
            vis[p] = 1;
    }

    cout << "! " << p << endl;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int t;
    cin >> t;
    while(t --)
        solve();

    return 0;
}