Submission #2116003

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, Q, A[2009], B[2009], dist[2009][2009]; vector<int>X[2009], S; bool used[2009];

void dfs(int pos, int fro, int depth) {
	if (used[pos] == true) return;
	used[pos] = true; dist[fro][pos] = depth;
	for (int i = 0; i < X[pos].size(); i++) {
		dfs(X[pos][i], fro, depth + 1);
	}
}

int main() {
	cin >> N >> Q;
	for (int i = 1; i <= N - 1; i++) {
		cin >> A[i] >> B[i];
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) used[j] = false;
		dfs(i, i, 0);
	}
	for (int i = 1; i <= N; i++) S.push_back(i);
	while (S.size() >= 2) {
		int maxn = (1 << 30); pair<int, int>maxid = make_pair(-1, -1);
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dist[i][j] > 2) continue;
				int s1 = 0, s2 = 0, s3 = 0;
				for (int k : S) {
					if (dist[i][k] < dist[j][k]) s1++;
					if (dist[i][k] > dist[j][k]) s2++;
					if (dist[i][k] == dist[j][k]) s3++;
				}
				if (maxn > max({ s1,s2,s3 })) {
					maxn = max({ s1,s2,s3 });
					maxid = make_pair(i, j);
				}
			}
		}
		cout << "? " << maxid.first << " " << maxid.second << endl;
		int V, a1 = maxid.first, a2 = maxid.second; cin >> V;
		vector<int>T;
		if (V == maxid.first) {
			for (int i : S) {
				if (dist[a1][i] < dist[a2][i]) T.push_back(i);
			}
		}
		else if (V == maxid.second) {
			for (int i : S) {
				if (dist[a1][i] > dist[a2][i]) T.push_back(i);
			}
		}
		else {
			for (int i : S) {
				if (dist[a1][i] == dist[a2][i]) T.push_back(i);
			}
		}
		S = T;
	}
	cout << "! " << S[0] << endl;
	return 0;
}

Submission Info

Judge Result