考虑按顺序插入点。直接进行点分治，从大到小遍历每个点的所有子树，假设当前的重心为 $u$，子树为 $v$，需要插入的点为 $i$。询问 $(i,u,v)$。通过答案可以直接判断 $i$ 所在的位置。这样的询问次数大约为 $\sum_{i=1}^N18\cdot\log_{18}i$，约为限制的两倍。考虑改为询问 $(i,v_1,v_2)$，其中 $v_1$, $v_2$ 是 $u$ 的两个不同的儿子。这样，如果答案为 $i$ 或未加入的点，只需要再花费一次询问即可确定位置。最坏情况的总询问次数大约为 $37000$。

#include "meetings.h"
#include <vector>
#include <set>
#include <algorithm>
#include <functional>
void Solve(int n) {
    std::vector<std::set<int>> e(n);
    std::vector<int> siz(n);
    std::vector<bool> vis(n);
    std::vector<bool> ins(n);
    auto link = [&](int u, int v) {
        e[u].insert(v);
        e[v].insert(u);
    };
    auto cut = [&](int u, int v) {
        e[u].erase(v);
        e[v].erase(u);
    };
    std::function<void(int, int)> dfs = [&](int u, int p) {
        siz[u] = 1;
        for (auto v : e[u]) {
            if (v == p || vis[v])
                continue;
            dfs(v, u);
            siz[u] += siz[v];
        }
    };
    std::function<int(int, int, int)> findCentroid = [&](int u, int p, int n) {
        for (auto v : e[u]) {
            if (v == p || vis[v])
                continue;
            if (2 * siz[v] > n)
                return findCentroid(v, u, n);
        }
        return u;
    };
    std::function<void(int, int)> work = [&](int r, int x) {
        dfs(r, -1);
        r = findCentroid(r, -1, siz[r]);
        dfs(r, -1);
        vis[r] = true;
        std::vector<int> ch;
        for (auto v : e[r])
            if (!vis[v])
                ch.push_back(v);
        std::sort(ch.begin(), ch.end(), [&](int u, int v) { return siz[u] > siz[v]; });
        for (int i = 0; i < int(ch.size()); ++i) {
            if (i + 1 < int(ch.size())) {
                int u = Query(ch[i], ch[i + 1], x);
                if (u == r) {
                    continue;
                } else if (u == ch[i]) {
                    return work(ch[i], x);
                } else if (u == ch[i + 1]) {
                    return work(ch[i + 1], x);
                } else if (u == x) {
                    link(r, x);
                    if (Query(r, ch[i], x) == x) {
                        cut(r, ch[i]);
                        link(ch[i], x);
                    } else {
                        cut(r, ch[i + 1]);
                        link(ch[i + 1], x);
                    }
                    return;
                } else {
                    link(u, x);
                    link(r, u);
                    ins[u] = true;
                    if (Query(r, ch[i], x) == u) {
                        cut(r, ch[i]);
                        link(ch[i], u);
                    } else {
                        cut(r, ch[i + 1]);
                        link(ch[i + 1], u);
                    }
                    return;
                }
            } else {
                int u = Query(r, ch[i], x);
                if (u == r) {
                    continue;
                } else if (u == ch[i]) {
                    return work(ch[i], x);
                } else if (u == x) {
                    cut(r, ch[i]);
                    link(r, x);
                    link(ch[i], x);
                    return;
                } else {
                    ins[u] = true;
                    cut(r, ch[i]);
                    link(r, u);
                    link(ch[i], u);
                    link(u, x);
                    return;
                }
            }
        }
        link(r, x);
    };
    ins[0] = true;
    for (int i = 1; i < n; ++i) {
        if (ins[i])
            continue;
        ins[i] = true;
        std::fill(vis.begin(), vis.end(), false);
        work(0, i);
    }
    for (int u = 0; u < n; ++u)
        for (auto v : e[u])
            if (u < v)
                Bridge(u, v);
}