题解：P10440 [JOISC 2024] 环岛旅行

· · 题解

来补篇题解 111

首先一种想法就是把 1 作为根，然后每次取距离 1 最远的点 u，然后依次访问距离 u 距离最近的点，这样第一个查到的没被取出过的点就是 u 的父亲，可以做到 3n 次询问。

const int N = 3e2 + 5;
int p[N], a[N], vis[N];
void solve(int n, int s) {
    ROF(i, n - 1, 1) {
        int u = query(1, i);
        FOR(j, 1, n) {
            int v = query(u, j);
            if(p[v] == u) continue;
            p[u] = v;
            break;
        }
    }
    FOR(i, 2, n) answer(p[i], i);
}

但是每次会查询一个点的所有邻居，而有用的信息只有其父亲，考虑充分利用信息。

还是将 1 作为根，但是这次每次取距离 1 最近的点 u，接下来，当 u 还没有确定其父亲的时候，就依次访问其最近的点，直到找到父亲为止。

这样的话，每次 u 可以查询到邻居 v，如果 v 被取出过，那么 v 就是 u 的父亲，反之，可以知道 u 是 v 的父亲。这样每次查询就能知道一对父子关系。

这样就做到了 2n 次询问。

const int N = 3e2 + 5;
int p[N], a[N], vis[N];
void solve(int n, int s) {
    vis[1] = 1;
    FOR(i, 1, n - 1) {
        int u = query(1, i);
        vis[u] = 1;
        int c = 0;
        while(! p[u]) {
            int v = query(u, ++ c);
            if(vis[v]) p[u] = v;
            else p[v] = u;
        }
    }
    FOR(i, 2, n) answer(p[i], i);
}