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

Задача . E. Деревянная игра

Задача

Темы: битмаски Деревья жадные алгоритмы математика *2000

Вам дан лес из $k$ корневых деревьев$^{\text{∗}}$. Дровосек Тимофей хочет вырубить весь лес, применяя такую операцию:

Выбрать поддерево$^{\text{†}}$ какой-либо вершины одного из деревьев и удалить его из дерева.

Тимофей очень любит битовые операции, поэтому он хочет, чтобы побитовое ИЛИ размеров поддеревьев, которые он удалял, было максимальным. Помогите ему и найдите, какой максимальный результат он может получить.

$^{\text{∗}}$ Деревом называется связный граф без циклов, петель и кратных ребер. Лесом называется набор из одного или нескольких деревьев. В корневом дереве одна из вершин называется корнем.

$^{\text{†}}$ Поддерево вершины $v$ — это множество вершин, для которых $v$ лежит на кратчайшем пути от этой вершины до корня, включая вершину $v$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $t$ ($1 \leq t \leq 10^4$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных содержит одно целое число $k$ ($1 \leq k \leq 10^6$) — количество деревьев в лесу.

Далее следует описание каждого из $k$ деревьев:

Первая строка содержит одно целое число $n$ ($1 \leq n \leq 10^6$) — размер дерева. Вершины дерева пронумерованы целыми числами от $1$ до $n$. Корнем дерева является вершина под номером $1$.

Вторая строка содержит $n - 1$ целое число $p_2, p_3, \ldots p_n$ ($1 \leq p_i < i$), где $p_i$ — предок вершины $i$.

Гарантируется, что сумма $k$ и $n$ по всем наборам входных данных не превосходит $10^6$.

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

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

Примечание

Во втором наборе входных данных деревья выглядят так:

$\text{[math]}$

Первой операцией удалим все второе дерево.

$\text{[math]}$

Второй операцией удалим вершину $4$ из первого дерева.

$\text{[math]}$

Третьей операцией удалим первое дерево. Результат равен $6|1|3 = 7$ ($|$ обозначает побитовое ИЛИ).

В третьем наборе входных данных нужно удалить все дерево.

Примеры

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

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

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

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

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

Ваш ответ

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

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

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

Нет