P12447 [COTS 2025] 砍树 / Stablo

· · 题解

有点意思的题。

考虑逐个加点。假设已经维护出来原树的一个连通块，我们现在要加入一个新点，即挂一个叶子到这个连通块上。

考虑边分治去找新点应该挂到哪个点上。每次找到一条边 (u, v) 使得它连接的两棵子树大小最大值最小。设新点为 x，询问一次 (x, u, v) 即可知道 x 在 u 子树内还是 v 子树内，扔掉另一棵子树然后继续做直到只剩一个点即可。由于树是二叉树所以对于一个 x 至多问 O(\log n) 次，加入 n 个点总共问 O(n \log n) 次。

问题还剩下如何保证新点一定是连通块的叶子。考虑将所有点按照与 1 的距离从小到大排序，依次加入即可。排序需要 O(n \log n) 次询问。

所以我们就以 O(n \log n) 的询问次数做完了。询问次数实际表现差不多是 2n \log n。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 520;

int n, p[maxn];
bool vis[maxn];
pii e[maxn];
vector<int> G[maxn];
map< pair< pair<int, int>, int >, int > mp;

inline int ask(int a, int b, int c) {
    if (mp.find(mkp(mkp(a, b), c)) != mp.end()) {
        return mp[mkp(mkp(a, b), c)];
    }
    printf("? %d %d %d\n", a, b, c);
    fflush(stdout);
    int x;
    scanf("%d", &x);
    return mp[mkp(mkp(a, b), c)] = x;
}

int sz[maxn], fa[maxn];

void dfs(int u, int t) {
    sz[u] = 1;
    fa[u] = t;
    for (int v : G[u]) {
        if (v == t || !vis[v]) {
            continue;
        }
        dfs(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int fa) {
    vis[u] = 0;
    for (int v : G[u]) {
        if (v == fa || !vis[v]) {
            continue;
        }
        dfs2(v, u);
    }
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
    }
    stable_sort(p + 2, p + n + 1, [&](const int &x, const int &y) {
        return ask(1, x, y) == 1;
    });
    G[1].pb(p[2]);
    G[p[2]].pb(1);
    e[1] = mkp(1, p[2]);
    for (int i = 3; i <= n; ++i) {
        mems(vis, 0);
        for (int j = 1; j < i; ++j) {
            vis[p[j]] = 1;
        }
        while (1) {
            int cnt = 0, u = 0;
            for (int j = 1; j < i; ++j) {
                if (vis[p[j]]) {
                    ++cnt;
                    u = p[j];
                }
            }
            if (cnt == 1) {
                e[i - 1] = mkp(u, p[i]);
                G[u].pb(p[i]);
                G[p[i]].pb(u);
                break;
            }
            dfs(u, -1);
            int mn = 1e9, w = -1;
            for (int j = 1; j < i; ++j) {
                int v = p[j];
                if (u != v && vis[v] && max(sz[v], cnt - sz[v]) < mn) {
                    mn = max(sz[v], cnt - sz[v]);
                    w = v;
                }
            }
            if (ask(p[i], w, fa[w]) == 1) {
                dfs2(fa[w], w);
            } else {
                dfs2(w, fa[w]);
            }
        }
    }
    puts("!");
    for (int i = 1; i < n; ++i) {
        printf("%d %d\n", e[i].fst, e[i].scd);
    }
}

int main() {
    int T = 1;
    // scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}