Олимпиадный тренинг

Задача . D. Вертикальные пути

Задача

Задано корневое дерево из $n$ вершин. Вершины пронумерованы от $1$ до $n$. Корнем может быть любая из вершин.

Дерево — это связный неориентированный граф без циклов. Корневое дерево — дерево с выделенной вершиной, которую называют корнем.

Дерево задано массивом предков $p$, содержащим $n$ целых чисел: $p_i$ — предок вершины с номером $i$. Предком вершины $u$ называется такая вершина, которая является следующей вершиной на кратчайшем пути от $u$ к корню. Например, на простом пути из $5$ в $3$ (корень), следующая вершина будет $1$, таким образом, предком вершины $5$ является вершина $1$.

У корня предка нет, для него в качестве $p_i$ используется значение $i$ (таким образом, корень — единственная вершина, для которой $p_i=i$).

Найдите такой набор путей, что:

каждая вершина принадлежит ровно одному пути, каждый путь может содержать одну или более вершину;
в каждом пути каждая очередная вершина — это сын текущей вершины (то есть пути всегда ведут вниз — от родителя к сыну);
количество путей минимально.

Например, если $n=5$ и $p=[3, 1, 3, 3, 1]$, то дерево можно разбить на три пути:

$3 \rightarrow 1 \rightarrow 5$ (путь из $3$ вершин),
$4$ (путь из $1$ вершины),
$2$ (путь из $1$ вершины).

$\text{[math]}$ Пример разбиения корневого дерева на три пути для $n=5$, корень дерева — вершина $3$.

Входные данные

В первой строке входных данных записано целое число $t$ ($1 \le t \le 10^4$) — количество наборов входных данных в тесте.

Каждый набор входных данных состоит из двух строк.

В первой из них записано целое число $n$ ($1 \le n \le 2 \cdot 10^5$) — количество вершин в дереве.

Во второй записано $n$ целых чисел $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Гарантируется, что массив $p$ кодирует некоторое корневое дерево.

Гарантируется, что сумма значений $n$ по всем наборам входных данных в тесте не превосходит $2 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных на первой строке выведите целое число $m$ — минимальное количество непересекающихся путей, идущих сверху вниз, которыми можно покрыть все вершины дерева.

Затем выведите $m$ пар строк, содержащих описания путей. В первую из них выведите длину пути, во второй — последовательность вершин, задающих этот путь в порядке сверху вниз. Вы можете выводить пути в любом порядке.

Если ответов несколько, выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	6 5 3 1 3 3 1 4 1 1 4 1 7 1 1 2 3 4 5 6 1 1 6 4 4 4 4 1 2 4 2 2 2 2	3 3 3 1 5 1 2 1 4 2 2 1 2 2 4 3 1 7 1 2 3 4 5 6 7 1 1 1 3 3 4 1 5 2 2 6 1 3 3 2 2 1 1 3 1 4

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет