docker_space/frontier_cs_10/solution.cpp

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

/*
 * Heavy-path tree reconstruction.
 * Step 1: Query d(1, v) for all v. (n-1 queries)
 * Step 2: Sort nodes by distance, process in order.
 * Step 3: For each node, find parent by querying heavy-path leaf of current tree.
 *         Uses O(log n) queries per node for random trees.
 * Total: ~n + n*O(log n) queries, well under 5n for random trees.
 */

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        if (n == 1) {
            cout << "!" << endl;
            continue;
        }

        if (n == 2) {
            cout << "? 1 2" << endl;
            long long d;
            cin >> d;
            cout << "! 1 2 " << d << endl;
            continue;
        }

        // Step 1: Query distances from root 1 to all others
        vector<long long> d1(n + 1, 0);
        for (int v = 2; v <= n; v++) {
            cout << "? 1 " << v << "\n";
            cout.flush();
            cin >> d1[v];
        }

        // Sort nodes by distance from root
        vector<int> order(n);
        iota(order.begin(), order.end(), 1);
        sort(order.begin(), order.end(), [&](int a, int b) {
            return d1[a] < d1[b];
        });

        // Tree structure
        vector<int> par(n + 1, 0);
        vector<vector<int>> children(n + 1);
        vector<int> sub_size(n + 1, 1);
        vector<int> heavy(n + 1, 0); // heavy child (0 = leaf)

        auto get_heavy_leaf = [&](int u) -> int {
            while (heavy[u] != 0) u = heavy[u];
            return u;
        };

        auto update_sizes = [&](int u) {
            int cur = par[u];
            int child = u;
            while (cur != 0) {
                sub_size[cur]++;
                if (heavy[cur] == 0 || sub_size[child] > sub_size[heavy[cur]]) {
                    heavy[cur] = child;
                }
                child = cur;
                cur = par[cur];
            }
        };

        vector<tuple<int,int,long long>> edges;

        for (int idx = 1; idx < n; idx++) {
            int v = order[idx];
            long long dv = d1[v];

            int cur = 1;
            int next_target = -1;
            long long next_d = -1;

            while (true) {
                int leaf;
                long long d_v_leaf;

                if (next_target != -1) {
                    leaf = next_target;
                    d_v_leaf = next_d;
                    next_target = -1;
                } else {
                    leaf = get_heavy_leaf(cur);
                    if (leaf == cur) {
                        // cur is a leaf in current tree, v attaches here
                        par[v] = cur;
                        children[cur].push_back(v);
                        edges.push_back({cur, v, (int)(dv - d1[cur])});
                        update_sizes(v);
                        break;
                    }
                    cout << "? " << v << " " << leaf << "\n";
                    cout.flush();
                    cin >> d_v_leaf;
                }

                // Compute LCA depth of v and leaf
                long long lca_d = (dv + d1[leaf] - d_v_leaf) / 2;

                // Walk up from leaf to find the LCA node
                int lca_node = leaf;
                int child_towards_leaf = 0;
                while (d1[lca_node] > lca_d) {
                    child_towards_leaf = lca_node;
                    lca_node = par[lca_node];
                }

                if (lca_node == leaf) {
                    par[v] = leaf;
                    children[leaf].push_back(v);
                    edges.push_back({leaf, v, (int)(dv - d1[leaf])});
                    update_sizes(v);
                    break;
                }

                // Check light children of lca_node (excluding the one toward leaf)
                vector<pair<int,int>> light_children;
                for (int c : children[lca_node]) {
                    if (c != child_towards_leaf) {
                        light_children.push_back({sub_size[c], c});
                    }
                }

                if (light_children.empty()) {
                    par[v] = lca_node;
                    children[lca_node].push_back(v);
                    edges.push_back({lca_node, v, (int)(dv - d1[lca_node])});
                    update_sizes(v);
                    break;
                }

                // Sort by size descending
                sort(light_children.rbegin(), light_children.rend());

                bool found = false;
                for (auto [sz, c] : light_children) {
                    int c_leaf = get_heavy_leaf(c);
                    cout << "? " << v << " " << c_leaf << "\n";
                    cout.flush();
                    long long d_v_cleaf;
                    cin >> d_v_cleaf;

                    long long lca2_d = (dv + d1[c_leaf] - d_v_cleaf) / 2;
                    if (lca2_d > d1[lca_node]) {
                        cur = c;
                        next_target = c_leaf;
                        next_d = d_v_cleaf;
                        found = true;
                        break;
                    }
                }

                if (!found) {
                    par[v] = lca_node;
                    children[lca_node].push_back(v);
                    edges.push_back({lca_node, v, (int)(dv - d1[lca_node])});
                    update_sizes(v);
                    break;
                }
            }
        }

        cout << "!";
        for (auto& [u, v, w] : edges) {
            cout << " " << u << " " << v << " " << w;
        }
        cout << "\n";
        cout.flush();
    }

    return 0;
}