「eJOI2022」寻找树根 / Where Is the Root? 题解

算法思路

本题使用二分查找和度数启发式排序来解决交互式树根定位问题。核心思想是通过对节点按度数排序，然后二分查找确定根节点的位置。

关键观察

1. 度数性质

• 根节点通常具有较高的度数（题目保证至少有一个节点度数 ≥ 3）
• 通过按度数排序，可以更有效地缩小搜索范围

2. LCA查询特性

• 如果查询集合包含根节点，则LCA在集合中（回答YES）
• 如果查询集合不包含根节点，则LCA不在集合中（回答NO）

代码解析

度数统计与排序

vector<int> d(n);  // 存储每个节点的度数
for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    d[u - 1]++, d[v - 1]++;  // 统计度数
}

vector<int> p(n);
iota(p.begin(), p.end(), 0);  // 初始化节点编号0到n-1
sort(p.begin(), p.end(), [&](int x, int y) {
    return d[x] < d[y];  // 按度数升序排序
});

交互查询函数

auto ask = [&](int x) {
    if (x) {
        cout << "? " << x + 1 << ' ';
        for (int i = 0; i <= x; i++)
            cout << p[i] + 1 << ' ';  // 查询前x+1个节点
    } else {
        cout << "? 2 " << p[0] + 1 << ' ' << p[2] + 1;  // 特殊处理小查询
    }
    cout << endl;
    string s;
    cin >> s;
    return s[0] == 'Y';  // 返回是否LCA在集合中
};

二分查找核心

int l = 0, r = n - 1;
while (l < r) {
    int m = l + r >> 1;  // 二分中点
    if (ask(m))
        r = m;    // LCA在集合中，根在前m+1个节点中
    else
        l = m + 1; // LCA不在集合中，根在后半部分
}
cout << "! " << p[r] + 1 << endl;  // 输出根节点

算法正确性

二分查找原理

• 初始搜索范围：所有节点 [0, n-1]
• 每次查询前 m+1 个节点（按度数排序）
• 如果回答YES：根节点在前 m+1 个节点中
• 如果回答NO：根节点在后 n-m-1 个节点中

度数排序的优势

• 根节点度数较高，更可能出现在排序后的前面位置
• 减少二分查找的迭代次数
• 符合题目对查询次数的评分要求

复杂度分析

• 度数统计：$O(n)$
• 排序：$O(n \log n)$
• 二分查找：$O(\log n)$ 次查询
• 总查询次数：$\lceil \log_2 n \rceil \leq 9$（对于 $n \leq 500$）

关键技巧

1. 度数启发式：利用根节点度数较高的特性优化搜索
2. 二分查找：在排序后的节点序列上进行二分
3. 交互优化：最小化查询次数以获得高分
4. 边界处理：特殊处理小规模查询情况