Задача 7. Экспедиция ≡

Условие

Планируется отправить экспедицию к соседней звёздной системе. Были отобраны n кандидатов, пронумерованных от 1 до n, среди которых необходимо выбрать участников экспедиции. Организаторы хотят отправить в экспедицию как можно больше кандидатов.

Среди кандидатов был проведён опрос, в процессе которого каждый мог указать не более, чем одного из остальных кандидатов, с которым он не готов отправиться в экспедицию. Результатом опроса для i-го кандидата является целое число a_i, которое равно номеру кандидата, с которым i-й кандидат не готов отправиться в экспедицию, либо  − 1, если i-й кандидат готов отправиться в экспедицию в любом составе.

Теперь организаторы должны выбрать, кто из кандидатов отправится в экспедицию. Решено было выбрать участников экспедиции так, что если туда входит некоторый кандидат i, и a_i ≠  − 1, то туда не входит кандидат a_i. Организаторы хотят выбрать максимальное количество участников экспедиции.

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

Формат входных данных

В первой строке входных данных находится целое число n  — количество кандидатов.

В следующих n строках даны результаты опроса, i-я из этих строк содержит результат опроса i-го кандидата, целое число a_i.

Формат выходных данных

В единственной строке выведите одно целое число  — максимальное количество кандидатов, которых можно отправить в экспедицию.

Ограничения

1 ≤ n ≤ 300 000

a_i =  − 1 или 1 ≤ a_i ≤ n, a_i ≠ i

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

4
2
4
2
1

2

3
2
-1
2

2

Разбор

Для решения подзадачи 1 можно перебрать все подмножества кандидатов и для каждого подмножества проверить, удовлетворяет ли оно требованиям к составу экспедиции. Время работы O(n2ⁿ).

В подзадаче 2 в экспедицию можно взять либо всех кандидатов с нечётными номерами, либо всех кандидатов с чётными номерами. Первое выгоднее, в этом случае в экспедицию отправятся ⌊ (n + 1) / 2⌋ кандидатов.

Для решения подзадач 3, 4 и 5 переформулируем задачу в терминах теории графов. Построим ориентированный граф, у которого вершинами будут кандидаты в экспедицию, проведем из вершины i ребро в вершину a_i, если a_i ≠  − 1. Условие, что в экспедицию нельзя одновременно брать кандидатов i и a_i соответствует тому, что множество отправленных в экспедицию кандидатов должно образовывать независимое множество в графе.

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

Рассмотрим теперь решение с использованием динамического программирования на подвешенном дереве: хоть и избыточное для задачи на дереве, оно пригодится нам для решения подзадач 4 и 5. Обозначим как with[u] размер максимального независимого множества в поддереве вершины u, содержащего вершину u, и как out[u] размер максимального независимого множества в поддереве вершины u, не содержащего вершину u. Тогда with[u] = ∑_{v − сын{u}} out[v], out[u] = ∑_{v − сын{u}}max(with[v], out[v]). Для листа with[u] = 1, out[u] = 0.

Теперь ответ для дерева равен max(with[r], out[r]) для корня дерева r.

Перейдем теперь к решению задачи для подзадач 4 и 5, где граф не обязан быть деревом. Заметим, что из каждой вершины выходит не более одного ребра. Каждая компонента связности такого графа представляет собой либо дерево, либо цикл, к каждой вершине которого может быть подвешено дерево. Решим задачу независимо для каждой компоненты связности и сложим ответы для них. Для компонент, которые представляют собой дерево, решение уже описано выше.

Рассмотрим теперь компоненту, которая содержит цикл. Удалим ребра цикла и решим задачу для каждого из получившихся деревьев. Осталось решить следующую задачу на цикле: в каждой вершине есть два числа: with[u] и out[u] требуется для каждой вершины цикла одно из этих чисел, причём для двух соседних вершин нельзя одновременно выбрать with. Для решения этой задачи можно использовать динамическое программирование, аналогичное решению задачи для дерева: разрежем одно из ребер цикла, переберем, какое из двух значений взято для первой вершины, посчитаем значения вдоль получившегося пути, и найдем ответ.

В зависимости от реализации всех описанных методов, за O(n²) или O(n), решение получает баллы за подзадачи 4 и 5.