题解：CF1534D Lost Tree

当成有权树做了一整天都没想出来（

首先需要注意到，存在边 $(i,j)$ 当且仅当 $d_{i,j} = 1$。

可以想一想我们怎么样可以不重不漏找到所有边，显然就是隔一个点问一个，这样把所有满足条件的 $d_{i,j}$ 都可以算作一个答案，一定不重复也不会遗漏。然后你发现树其实就是个二分图，黑点和白点个数肯定有一个小于 $\frac{n}{2}$，然后这题做完了，找到点数更小的一个颜色查询就做完啦。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<int> ask(int x)
{
    cout << "? " << x << '\n';
    cout.flush();
    vector<int> d(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }
    return d;
}
void answer(vector<pair<int, int>> ans)
{
    cout << "!\n";
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i].first << ' ' << ans[i].second << '\n';
        cout.flush();
    }
}
signed main()
{
    cin >> n;
    auto tp = ask(1);
    vector<vector<int>> a(n + 1);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (tp[i] % 2 == 0) {
            cnt++;
        }
    }
    a[1] = tp;
    for (int i = 2; i <= n; i++) {
        if (cnt <= n - cnt) {
            if (tp[i] % 2 == 0) {
                a[i] = ask(i);
            }
        } else {
            if (tp[i] % 2 == 1) {
                a[i] = ask(i);
            }
        }
    }
    vector<pair<int, int>> ans;
    for (int i = 1; i <= n; i++) {
        if (cnt > n - cnt && i == 1) {
            continue;
        }
        if (a[i].size()) {
            for (int j = 1; j <= n; j++) {
                if (a[i][j] == 1) {
                    ans.push_back({i, j});
                }
            }
        }
    }
    answer(ans);
    return 0;
}