Pinely Round 1 (Div. 1 + Div. 2) |
---|
Закончено |
Это интерактивная задача.
Есть загаданное дерево, состоящее из $$$n$$$ вершин, которое имеет только один центроид. Сначала вам известно только $$$n$$$, и ваша задача — найти центроид дерева.
Вы можете спросить расстояние между любыми двумя вершинами не более $$$2\cdot10^5$$$ раз.
Обратите внимание, что интерактор является неадаптивным. То есть, дерево фиксировано в каждом тесте заранее и не зависит от ваших запросов.
Вершина называется центроидом, если ее удаление разбивает дерево на поддеревья, в каждом из которых не более $$$\lfloor\frac{n}{2}\rfloor$$$ вершин.
Единственная строка ввода содержит целое число $$$n$$$ ($$$3\le n\le 7.5\cdot10^4$$$) — количество вершин в дереве.
Начните взаимодействие с чтения $$$n$$$.
Чтобы задать запрос о расстоянии между двумя вершинами $$$u, v$$$ ($$$1 \le u, v \le n$$$), выведите «? u v».
Если вы определили, что центроидом дерева является $$$x$$$, используйте «! x» для вывода ответа.
После вывода запроса не забудьте вывести конец строки и сбросить буфер вывода. В противном случае вы получите Решение «зависло». Для этого используйте:
В этой задаче взломы отключены.
Гарантируется, что в этой задаче есть не более $$$500$$$ тестов.
5 2 1 2 3 1 1 1
? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 2 3 ? 3 4 ? 4 5 ! 3
Вот изображение дерева из примера.
Название |
---|