Задача №114681. Найти путь
Дано дерево (связный неориентированный граф без циклов), состоящее из \(n\) вершин. Для пары вершин \(u\) и \(v\) обозначим за \(f(u, v)\) последовательность номеров вершин на единственном пути из вершины \(u\) в вершину \(v\) в порядке от \(u\) к \(v\). Например, для любого ребра \((u, v)\) дерева \(f(u, v) = [u, v]\), а для любой вершины \(u\) дерева \(f(u, u) = [u]\).
Для данного дерева выписали все \(n^2\) последовательностей \(f(i, j)\) для всевозможных пар \(1 \leq i, j \leq n\) и упорядочили эти последовательности лексикографически.
Даны \(q\) запросов, каждый из которых состоит из единственного числа \(k\). Для каждого запроса определите пару вершин \(u\) и \(v\), путь между которыми оказался в полученном списке последовательностей на \(k\)-м месте. Последовательности в списке нумеруются, начиная с 1.
В первой строке содержатся два целых числа \(n\) и \(q\) (\(1 \leq n \leq 100\,000, 1 \leq q \leq 300\,000\)) — количество вершин в дереве и количество запросов, соответственно.
В следующих \(n - 1\) строках содержатся пары целых чисел \(u_i, v_i\) (\(1 \leq u_i, v_i \leq n\)), описывающие ребра между вершинами \(u_i\) и \(v_i\). Гарантируется, что заданный граф является деревом.
В следующих \(q\) строках содержатся описания запросов. Запрос задаётся единственным числом \(k\) (\(1 \leq k \leq n^2\)) — номером пути в списке, чьи конечные вершины требуется найти.
Для каждого запроса выведите ответ на него в отдельной строке: если на позиции \(k\) в списке последовательностей находится \(f(u, v)\), выведите \(u\) и \(v\).
В примере существуют такие последовательности:
\(\)[1], [1, 2], [1, 2, 3],\(\) \(\)[2], [2, 1], [2, 3],\(\) \(\)[3],[3, 2], [3, 2, 1]\(\)
Последовательность \(a\) длины \(n\) лексикографически меньше последовательности \(b\) длины \(m\) тогда и только тогда, когда существует \(i \leq \min(n, m)\) такое, что \(a_j = b_j\) для всех \(j \lt i\) и \(a_i \lt b_i\) или когда \(n \lt m\) и \(a_i = b_i\) для всех \(i \leq n\).
Обратите внимание, что число \(k\) может превышать размер \(32\)-битного типа данных.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
Обозначим за \(d_v\) степень вершины \(v\) — количество вершин, с которыми \(v\) соединена ребром.
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(q\) | \(k\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 11 | \(n \le 100\) | \(q \le 10\,000\) | – | 0 | |
| 2 | 15 | \(n \le 1000\) | \(q \le 10\,000\) | – | 0 – 1 | |
| 3 | 12 | – | – | – | – | \(d_v = 1\) ровно у двух вершин. |
| 4 | 12 | – | – | – | – | \(d_v = 1\) ровно у \(n - 1\) вершин. |
| 5 | 25 | – | – | \(k \le n\) | – | |
| 6 | 25 | – | – | – | 0 – 5 | |
3 4 1 2 2 3 1 5 2 9
1 1 2 1 1 2 3 1