Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Think in terms of vertices already proven not to be on the hidden path. A 0 answer to ? a b kills every vertex on the path from to .
A 1 answer is only really useful when the queried path contains very few still-possible vertices. Try to make every query path contain exactly two live vertices.
If the current query path has only two live endpoints and the answer is 1, then one extra query ? a a resolves it: if that is 1, output ; otherwise output .
So the whole problem becomes: pair the vertices in an order where, when a pair is queried, all internal vertices on their connecting path were paired earlier.
Pick any edge as the first pair. Root the two sides at its endpoints, list all remaining vertices by increasing distance from that edge, and pair consecutive vertices. Internal vertices of each such path have smaller distance, so after earlier 0 answers they are already dead.
The key is to stop trying to find the whole hidden path. That is overkill. We only need one vertex on it, and the query limit screams that each negative query should eliminate about two vertices.
Call a vertex dead if previous answers already prove it is not on the hidden path. If we query a path whose only non-dead vertices are exactly two endpoints and , then the answer is perfect:
0, both and become dead.1, the hidden path must contain or , because every internal vertex is already dead. Then query ? a a; if it returns 1, output , otherwise output .So now we just need a way to order the vertices into pairs with this property.
Choose any edge of the tree. This is the first pair. Its path has no internal vertices, so it is valid immediately.
Now view the tree as rooted from this edge: set
and for every other vertex , let be its distance from the nearer endpoint of that initial edge. Equivalently, remove the edge and root the two resulting components at and .
List all vertices except in nondecreasing order of . Pair consecutive vertices in this list. If one vertex is left over, keep it as the final leftover.
Why does this work? Take any later pair , with immediately before in this depth order. Consider any internal vertex on the path from to .
In this two-rooted tree, depths along a path move toward the root side and then away from it, so no internal vertex can be deeper than the deeper endpoint. In fact, every internal vertex appears earlier than in the nondecreasing depth order. Since is immediately before , any such internal vertex is either or appears before . It cannot be because is an endpoint, not internal. Therefore every internal vertex was processed in an earlier pair.
Now maintain the invariant:
Before querying a pair , every internal vertex on the path is dead.
The first edge satisfies this trivially. If a pair query returns 0, the entire queried path is disjoint from the hidden path, so the new endpoints also become dead and the invariant continues. If it returns 1, the hidden path intersects the query path, but the internal vertices are dead, so the intersection must include or . One singleton query identifies a guaranteed answer.
What if all pair queries return 0? This can only happen when is odd, because then exactly one vertex was left unpaired. Every other vertex is dead, but the hidden path is nonempty, so the leftover vertex must be on it. Output it.
The number of pair queries is exactly . If some pair gets answer 1, we spend one more singleton query, for a total of at most
The construction is linear with BFS from the two endpoints of the first edge, and the query count matches the required bound. Clean, slightly sneaky, and very much not a binary search. Binary search gets bullied by the adaptive interactor here.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
int r = 1, s = g[1][0];
vector<int> dist(n + 1, -1), order;
queue<int> q;
dist[r] = dist[s] = 0;
q.push(r);
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int to : g[v]) {
if (dist[to] == -1) {
dist[to] = dist[v] + 1;
order.push_back(to);
q.push(to);
}
}
}
vector<pair<int, int>> pairs;
pairs.push_back({r, s});
for (int i = 0; i + 1 < (int)order.size(); i += 2) {
pairs.push_back({order[i], order[i + 1]});
}
int leftover = ((int)order.size() % 2 ? order.back() : -1);
auto ask = [&](int a, int b) -> int {
cout << "? " << a << ' ' << b << '\n';
cout.flush();
int res;
cin >> res;
if (res == -1) exit(0);
return res;
};
auto answer = [&](int v) {
cout << "! " << v << '\n';
cout.flush();
};
bool done = false;
for (auto [a, b] : pairs) {
int res = ask(a, b);
if (res == 1) {
if (ask(a, a) == 1) answer(a);
else answer(b);
done = true;
break;
}
}
if (!done) {
answer(leftover == -1 ? 1 : leftover);
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
int r = 1, s = g[1][0];
vector<int> dist(n + 1, -1), order;
queue<int> q;
dist[r] = dist[s] = 0;
q.push(r);
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int to : g[v]) {
if (dist[to] == -1) {
dist[to] = dist[v] + 1;
order.push_back(to);
q.push(to);
}
}
}
vector<pair<int, int>> pairs;
pairs.push_back({r, s});
for (int i = 0; i + 1 < (int)order.size(); i += 2) {
pairs.push_back({order[i], order[i + 1]});
}
int leftover = ((int)order.size() % 2 ? order.back() : -1);
auto ask = [&](int a, int b) -> int {
cout << "? " << a << ' ' << b << '\n';
cout.flush();
int res;
cin >> res;
if (res == -1) exit(0);
return res;
};
auto answer = [&](int v) {
cout << "! " << v << '\n';
cout.flush();
};
bool done = false;
for (auto [a, b] : pairs) {
int res = ask(a, b);
if (res == 1) {
if (ask(a, a) == 1) answer(a);
else answer(b);
done = true;
break;
}
}
if (!done) {
answer(leftover == -1 ? 1 : leftover);
}
}
return 0;
}