题解：P10440 [JOIST 2024] 环岛旅行 / Island Hopping

· · 题解

好像比较显然。

一条边一定是父子关系，记为 (i, fa_i)，那么我们只需要得到每个点的父亲即可解决此题，令根为 1，考虑对于一个点 u 如何求出 fa_u。

先想想求 fa 的顺序是什么：自底向上还是自顶向下。一个点可能有多个儿子，但只会有一个父亲，这样看来还是自顶向下做比较好（注意我们已知的是 u）。

这使得我们查询出 u 的祖先节点 v 时，v 定然已被访问过，而我们知道在祖先序列中 fa_u 是距 u 最近的，故而最近的被访问节点便是 fa_u。又因为此边权为 1，相同的距离只可能是儿子，换句话说我们从低往高查询 \text{query}(u, j)，fa_u 前被访问到的节点只会是 u 儿子，这又可以连边。

现在审视代码复杂度：我们从 1 至 n - 1 枚举每个点 \text{query}(1, i)，接下来的查询每次都会添加一条边，而总边数 n - 1，所以总的查询次数为 2n - 2，完全足以通过。

#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int fa[N];bool vis[N];
int query(int v, int k);
void answer(int x, int y);
void solve(int N, int L){
    vis[1] = 1;
    for (int i = 1; i < N; i ++){
        int u = query(1, i), j = 1;
        vis[u] = 1;
        while (!fa[u]){
            int x = query(u, j ++);
            (vis[x] ? fa[u] = x : fa[x] = u);
        }
    }for (int i = 2; i <= N; i ++)
        answer(i, fa[i]);
}

第一次写交互\bx