终点 - 交互题解题思路与 C++ 代码实现

题目背景

出题人怎么还没鸟加这首歌啊。

题目描述

这是一道交互题。

dXqwq 有一棵 (n) 个点的有根树，结点从 (1) 到 (n) 编号。您需要通过若干次询问得到这棵树的结构。

您可以选择两个整数 (1 \leq u,v \leq n)，并输出 ? u v 进行询问。

对于每次询问，如果 (u,v) 的路径中点在一个结点上，交互库返回该点的编号，否则返回 0。

请通过不超过 (147154) 次询问，得到这棵树的结构。

保证树的形态是提前确定的，即交互库不自适应。

交互方式

输入测试点所在子任务编号 (id) 和树的大小 (n) 以开始交互。

交互过程中，您可以进行题目描述中的询问。

对于每次询问，如果你提供的 (u,v) 不合法或者超出询问次数上限，交互库会返回 -1，否则交互库将会返回一个非负整数，含义见「题目描述」。

当你读取到 -1 后应立刻退出程序，在此之后交互库的行为未定义。

在您确定答案后，请先输出 !，然后接下来 (n-1) 行依次输出两个整数 u[i] v[i] 代表树的每条边，最后退出程序。你可以以任意顺序输出这些边。

在您输出一行后，请清空缓冲区：

在 C++ 中，使用 fflush(stdout) 或 cout.flush()。
在 Pascal 中，使用 flush(output)。
在 Python 中，使用 stdout.flush()。
其它语言请自行查阅文档。

输入格式

见「交互方式」。

输出格式

见「交互方式」。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

本题采用捆绑测试。

Subtask 1（10 pts）：(n \leq 10)，树满足性质 A。
Subtask 2（10 pts）：保证存在一个点度数为 (n-1)。
Subtask 3（10 pts）：保证所有点度数 (\leq 2)。
Subtask 4（10 pts）：(n \leq 500)，树满足性质 A。
Subtask 5（20 pts）：(n \leq 500)。
Subtask 6（20 pts）：树满足性质 A。
Subtask 7（20 pts）：无特殊限制。

性质 A：对于 (i=2,3,\cdots,n) 存在整数 (1 \leq j<i) 满足有一条边连接 (i,j)。

对于 (100%) 的数据，(2 \leq n \leq 10^4)。用C++做出这道题内容：```cpp #include #include

using namespace std;

int main() { int id, n; cin >> id >> n;

vector<int> deg(n + 1, 0);

// Step 1: Find a leaf node
int leaf = -1;
for (int i = 2; i <= n; i++) {
    cout << '? ' << i << ' 1' << endl;
    int res;
    cin >> res;
    if (res == 0) {
        leaf = i;
        break;
    }
    deg[res]++;
}

// Step 2: Find the parent of the leaf node
int parent = -1;
for (int i = 1; i <= n; i++) {
    if (deg[i] == 0 && i != leaf) {
        cout << '? ' << leaf << ' ' << i << endl;
        int res;
        cin >> res;
        if (res != 0) {
            parent = res;
            break;
        }
    }
}

// Step 3: Process the remaining nodes
for (int i = 1; i <= n; i++) {
    if (i == leaf) {
        continue;
    }
    cout << '? ' << leaf << ' ' << i << endl;
    int res;
    cin >> res;
    if (res == 0) {
        cout << '? ' << parent << ' ' << i << endl;
        cin >> res;
    }
    deg[res]++;
}

// Step 4: Output the edges
cout << '!' << endl;
for (int i = 1; i <= n; i++) {
    if (i != parent) {
        cout << parent << ' ' << i << endl;
    }
}

return 0;

} ``