Задача №114704. Найти вершину
Это интерактивная задача.
Вам дано дерево — связный неориентированный граф без циклов. В нём загадали одну из вершин. Вы можете задавать вопросы интерактору: за один вопрос вы можете выбрать ребро и узнать, какой из двух концов ребра находится ближе к загаданной вершине, то есть, до какого из двух концов меньше кратчайшее расстояние от загаданной вершины. Вам требуется определить загаданную вершину за минимальное для данного дерева число запросов в худшем случае.
Обратите внимание, что загаданная вершина может быть не фиксирована интерактором заранее: в зависимости от ваших запросов он может менять её на любую другую, с условием, что это не противоречит ответам на предыдущие запросы.
В первой строке входных данных содержится целое число \(n\) (\(2 \le n \le 100\)) — количество вершин в дереве.
В каждой из следующих \(n-1\) строк записаны два целых числа \(u\) и \(v\) (\(1 \le u, v \le n\)), обозначающих ребро между вершинами \(u\) и \(v\). Гарантируется, что данные ребра образуют дерево.
После считывания выходных данных вы можете отправлять интерактору запросы двух типов:
-
«
? \(u\) \(v\)
» — узнать для ребра дерева \((u, v)\) (\(1 \le u, v \le n\)), какой из его концов ближе к загаданной вершине. В ответ вы получите одно число: номер одной из двух вершин. Обратите внимание, что \(u\) и \(v\) должны быть соединены ребром в дереве, поэтому они не могут находиться на равном расстоянии от загаданной вершины.
- « ! \(u\) » — сообщить интерактору о том, что вы выяснили номер загаданной вершины. После вывода этой команды ваша программа должна немедленно завершиться.
После каждого вопроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Idleness Limit Exceeded или Превышено реальное время работы . Для сброса буфера вы можете использовать:
- fflush(stdout) или cout.flush() в C++ ;
- System.out.flush() в Java ;
- flush(output) в Pascal ;
- sys.stdout.flush() в Python ;
- смотрите документацию для других языков.
В случае, если вы сделаете большее число запросов, чем может быть необходимо для данного дерева в худшем случае, вы получите вердикт Неправильный ответ .
5 1 2 2 3 3 4 4 5
3 3 1
5 2 1 3 1 4 1 5 1
4 4 1