一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
E2 - Catch the Mole(Hard Version)
二、解题报告
1、思路分析
考虑每次误判都会让鼹鼠上升一层，相应的，最外层的一层结点都没用了
由于数据范围为5000，我们随便找个叶子结点询问71次，那么会剩下不超过70条路径
为什么呢？
剩下的路径一定满足长度大于71，路径数乘长度 <= 5000，故不超过70条
我们考虑在70条中找到鼹鼠所在的那一条然后在路上二分
我们还剩90次机会，路上二分最多十几次，我们如何70次内找到路径？
考虑直接深搜
由于剩余不超过70条路径，所以我们实际最多也就走70个分叉（再多路径就大于70条了）
然后有个注意的点，如果当前儿子结点为最后一个结点，我们直接进去深搜，这既正确的同时也是为了防止被单链样例卡掉
2、复杂度
时间复杂度： O(N + M + NlogN)空间复杂度：O(N + M)
3、代码详解
#include <bits/stdc++.h>
#define sc scanf
using i64 = long long;
using PII = std::pair<int, int>;
constexpr int inf32 = 1e9 + 7;
constexpr i64 inf64 = 1e18 + 7;// #define DEBUGint query(int x)
{std::cout << "? " << x + 1 << std::endl;int res;std::cin >> res;return res;
}constexpr int B = 71;void solve()
{int n;std::cin >> n;std::vector<std::vector<int>> adj(n);for (int i = 1, u, v; i < n; ++i){std::cin >> u >> v;--u, --v;adj[u].push_back(v);adj[v].push_back(u);}std::vector<int> h(n), fa(n, -1);auto dfs = [&](auto &&self, int u) -> void{for (int v : adj[u]){if (v == fa[u])continue;fa[v] = u;self(self, v);h[u] = std::max(h[u], h[v] + 1);}};dfs(dfs, 0);int leaf = std::find(h.begin(), h.end(), 0) - h.begin();for (int i = 0; i < B; ++i){if (query(leaf) == 1){std::cout << "! " << leaf + 1 << std::endl;return;}}auto find = [&](auto &&self, int u) -> int{std::vector<int> a;for (int v : adj[u]){if (v == fa[u] || h[v] < B)continue;a.push_back(v);}if (!a.size())return u;for (int v : a){if (v == a.back() || query(v) == 1)return self(self, v);}assert(false);return -1;};int v = find(find, 0);std::vector<int> a;for (; ~v; v = fa[v])a.push_back(v);std::reverse(a.begin(), a.end());int lo = 0, hi = a.size() - 1;while (lo < hi){int x = (lo + hi + 1) / 2;if (query(a[x]) == 1)lo = x;else{hi = x - 1;lo = std::max(0, lo - 1);hi = std::max(0, hi - 1);}}std::cout << "! " << a[lo] + 1 << std::endl;
}int main()
{
#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);int _ = 1;std::cin >> _;while (_--)solve();return 0;
}