题目背景

这是一道交互题。

题目描述

有一棵以 1 为根的 n 个点的有根树，您需要通过若干次询问得到这棵树的结构。

您可以使用两种询问：

1. ? 1 u v 通过这种询问，您可以获得 u 和 v 之间的距离。
2. ? 2 u 通过这种询问，您可以获得 u 子树的大小和 u 子树中的所有节点。

请通过使交互库输出不超过 40000 个数，得到这棵树的结构。

交互方式

输入树的大小 n 以开始交互。

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

对于第一种询问，交互库将会返回一个非负整数，表示 u 节点和 v 节点间的距离。

对于第二种询问，交互库将会先返回一个正整数 num，表示 u 子树的大小。接下来会在同一行中返回 num 个正整数，表示 u 子树中的所有节点（节点顺序会被打乱）。

在您确定答案后，请以 ! fa[2] fa[3] ... fa[n] 的形式输出一行，停止交互。其中 fa[i] 表示这棵树中 i 号节点的父节点。

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

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

输入格式

见「交互方式」。

输出格式

见「交互方式」。

输入输出样例

输入 #1

5

1

5 1 5 2 4 3

3 4 2 5

1 3

输出 #1

? 1 1 2

? 2 1

? 2 2

? 2 3

! 1 1 2 2

说明/提示

对于 100% 的数据：2≤n≤5000，1≤u,v≤n。

C++ 版交互题解：确定有根树结构

下面为您提供 C++ 版本的解题代码及详细解析，解决通过交互确定有根树结构的问题。

解题思路

与 Python 版本相同，我们采用广度优先搜索 (BFS) 策略：

1. 从根节点 (1) 开始，使用第二种询问获取其所有子树节点
2. 对于每个节点，识别其直接子节点（这些节点在当前节点子树中，但不在任何已确定子节点的子树中）
3. 递归处理每个直接子节点，直到确定所有节点的父节点

该方法仅需 n 次第二种询问，完全在 40000 的限制范围内。

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

int main() {
    // 关闭同步，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取树的大小
    int n;
    cin >> n;
    
    // 特殊情况：只有根节点
    if (n == 1) {
        cout << "!\n";
        cout.flush();
        return 0;
    }
    
    // 存储每个节点的父节点，fa[1]无意义（根节点没有父节点）
    vector<int> fa(n + 1, 0);
    
    // 存储每个节点的子树节点集合
    vector<unordered_set<int>> subtree(n + 1);
    
    // 标记节点是否已确定父节点
    vector<bool> determined(n + 1, false);
    determined[1] = true;  // 根节点没有父节点，视为已确定
    
    // BFS队列，从根节点开始处理
    queue<int> q;
    q.push(1);
    
    // 获取根节点的子树
    cout << "? 2 1\n";
    cout.flush();
    int num;
    cin >> num;
    for (int i = 0; i < num; ++i) {
        int node;
        cin >> node;
        subtree[1].insert(node);
    }
    
    // 广度优先搜索确定每个节点的父节点
    while (!q.empty()) {
        // 取出当前要处理的节点
        int current = q.front();
        q.pop();
        
        // 收集候选子节点：在当前节点子树中且未确定父节点的节点
        vector<int> candidates;
        for (int node : subtree[current]) {
            if (!determined[node]) {
                candidates.push_back(node);
            }
        }
        
        // 检查每个候选节点是否为当前节点的直接子节点
        for (int candidate : candidates) {
            // 标记是否在某个已确定子节点的子树中
            bool in_child_subtree = false;
            
            // 遍历当前队列中的节点（已确定为current的子节点）
            // 为了遍历队列，我们需要创建一个临时副本
            queue<int> temp_q = q;
            while (!temp_q.empty()) {
                int child = temp_q.front();
                temp_q.pop();
                
                if (subtree[child].count(candidate)) {
                    in_child_subtree = true;
                    break;
                }
            }
            
            // 如果不在任何已确定子节点的子树中，则是直接子节点
            if (!in_child_subtree) {
                fa[candidate] = current;
                determined[candidate] = true;
                
                // 获取该子节点的子树
                cout << "? 2 " << candidate << "\n";
                cout.flush();
                int child_num;
                cin >> child_num;
                for (int i = 0; i < child_num; ++i) {
                    int node;
                    cin >> node;
                    subtree[candidate].insert(node);
                }
                
                // 将该子节点加入队列，处理其后代
                q.push(candidate);
            }
        }
    }
    
    // 输出结果
    cout << "! ";
    for (int i = 2; i <= n; ++i) {
        cout << fa[i] << " ";
    }
    cout << "\n";
    cout.flush();
    
    return 0;
}

代码解析

1. 初始化部分

ios::sync_with_stdio(false);
cin.tie(nullptr);

这两行代码用于关闭 C++ 标准输入输出与 C 语言标准输入输出的同步，显著提高输入输出效率，对于交互题尤为重要。

int n;
cin >> n;

if (n == 1) {
    cout << "!\n";
    cout.flush();
    return 0;
}

读取树的大小 n，并处理特殊情况：当只有根节点时，直接输出结果。

2. 数据结构定义

vector<int> fa(n + 1, 0);  // 存储父节点信息
vector<unordered_set<int>> subtree(n + 1);  // 存储每个节点的子树
vector<bool> determined(n + 1, false);  // 标记节点是否已确定父节点
queue<int> q;  // BFS队列

• fa数组：fa[i]表示节点 i 的父节点
• subtree数组：每个元素是一个哈希集合，存储对应节点的子树中所有节点
• determined数组：标记节点是否已确定父节点
• q队列：用于 BFS 遍历，存储待处理的节点

3. 根节点处理

determined[1] = true;
q.push(1);

// 获取根节点的子树
cout << "? 2 1\n";
cout.flush();
int num;
cin >> num;
for (int i = 0; i < num; ++i) {
    int node;
    cin >> node;
    subtree[1].insert(node);
}

初始化根节点状态，将其加入队列，并使用第二种询问获取根节点的子树信息。

4. BFS 主循环

while (!q.empty()) {
    int current = q.front();
    q.pop();
    // ... 处理当前节点
}

循环处理队列中的每个节点，直到所有节点都被处理。

5. 候选子节点筛选

vector<int> candidates;
for (int node : subtree[current]) {
    if (!determined[node]) {
        candidates.push_back(node);
    }
}

收集当前节点子树中所有尚未确定父节点的节点作为候选子节点。

6. 直接子节点确定

for (int candidate : candidates) {
    bool in_child_subtree = false;
    
    queue<int> temp_q = q;
    while (!temp_q.empty()) {
        int child = temp_q.front();
        temp_q.pop();
        
        if (subtree[child].count(candidate)) {
            in_child_subtree = true;
            break;
        }
    }
    
    if (!in_child_subtree) {
        // 确定为直接子节点，更新信息
        // ...
    }
}

这部分是算法的核心：对于每个候选节点，检查它是否属于当前节点已确定的子节点的子树。如果不属于任何已确定子节点的子树，则它就是当前节点的直接子节点。

7. 结果输出

cout << "! ";
for (int i = 2; i <= n; ++i) {
    cout << fa[i] << " ";
}
cout << "\n";
cout.flush();

按照题目要求的格式输出节点 2 到 n 的父节点信息。

算法复杂度分析

• 时间复杂度：O (n²)，对于每个节点，我们可能需要检查它是否在其他节点的子树中
• 空间复杂度：O (n²)，最坏情况下每个节点的子树信息需要存储 O (n) 个节点
• 询问次数：正好 n 次（每个节点使用一次第二种询问），远低于 40000 的限制

该算法通过合理利用第二种询问和 BFS 策略，高效地确定了树的结构，完全满足题目的要求。在实现上，C++ 版本利用了哈希集合的快速查找特性，确保了算法的高效性。