Технокубок 2020 - Отборочный Раунд 2 |
---|
Закончено |
Байтландская фабрика деревьев производит деревья для всевозможных промышленных применений. Вам требуется соптимизировать построение дерева определённого типа для большого и важного заказа.
Нужное дерево является подвешенным деревом с $$$n$$$ вершинами, и его вершины пронумерованы различными числами от $$$0$$$ до $$$n - 1$$$. Вершина с номером $$$0$$$ является корнем дерева, и для любой некорневой вершины $$$v$$$ номер её родителя $$$p(v)$$$ меньше номера $$$v$$$.
Все деревья на фабрике делаются из заготовок-бамбуков. Бамбук — это такое корневое дерево, что каждая вершина имеет ровно одного сына, кроме единственной вершины-листа, у которой нет детей. Вершины бамбука-заготовки могут быть пронумерованы как угодно до начала обработки.
Чтобы превратить бамбук в нужное дерево, вы можете применять один тип операций: выбрать произвольную некорневую вершину $$$v$$$, такую что её родитель $$$p(v)$$$ также не является корнем. Операция состоит в изменении родителя $$$v$$$ на родителя его родителя $$$p(p(v))$$$. Родители всех остальных вершин остаются без изменений, в частности, поддерево $$$v$$$ не меняется.
Эффективность крайне важна, поэтому вам требуется минимизировать количество операций для превращения бамбука-заготовки в нужное дерево. Постройте любую оптимальную последовательность операций.
Обратите внимание, что нумерация вершин в полученном дереве должна совпадать с нумерацией в данном дереве. Формально, номера корней должны совпадать, а также для некорневых вершин с одинаковыми номерами должны совпадать номера их родителей.
Гарантируется, что во всех тестах к этой задаче ответ существует, и, более того, в оптимальной последовательности не более $$$10^6$$$ операций. Обратите внимание, что любой взлом, не удовлетворяющий этим ограничениям, будет некорректным.
В первой строке записано единственное целое число $$$n$$$ — количество вершин дерева ($$$2 \leq n \leq 10^5$$$).
Во второй строке записано $$$n - 1$$$ целое число $$$p(1), \ldots, p(n - 1)$$$ — номера родителей вершин $$$1, \ldots, n - 1$$$ соответственно ($$$0 \leq p(i) < i$$$).
В первой строке выведите $$$n$$$ различных целых чисел $$$id_1, \ldots, id_n$$$ — изначальная нумерация вершин бамбука-заготовки, начиная с корня ($$$0 \leq id_i < n$$$).
Во второй строке выведите одно целое число $$$k$$$ — количество операций в вашей последовательности ($$$0 \leq k \leq 10^6$$$).
В третьей строке выведите $$$k$$$ целых чисел $$$v_1, \ldots, v_k$$$, описывающих операции по порядку. $$$i$$$-я операция состоит в изменении $$$p(v_i)$$$ на $$$p(p(v_i))$$$. Каждая операция должна быть корректной, т.е. $$$v_i$$$ и $$$p(v_i)$$$ на момент операции не могут быть корнем.
5 0 0 1 1
0 2 1 4 3 2 1 3
4 0 1 2
0 1 2 3 0
Название |
---|