ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Петрозаводск лето 2018. t.me/umnik_team Contest

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Средний вес дерева

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Пусть есть помеченное дерево, то есть вершины дерева пронумерованы от 1 до n.
Определим вес дерева так: сумма по всем ребрам (uv) величин u · szuv(u) + v · szvu(v). Здесь szvu(v) — это размер того поддерева, в котором окажется v после удаления ребра (vu).
Дан массив a размера n. Элементы массива либо являются целыми числами от 1 до n−1, либо равны −1. v-й элемент соответствует степени вершины v. Назовём дерево размера n хорошим, если для всех v таких, что av ≠ −1, верно, что степень вершины v равна av. Другими словами, если av = −1, то степень вершины v может быть любой, а иначе степень фиксирована и равна av.
Выберем одно хорошее дерево случайно и равновероятно. Пусть E — матожидание веса этого дерева. Найдите целую часть E.

Исходные данные

В первой строке записано одно число n — размер дерева (2 ≤ n ≤ 106).
Во второй строке записан массив длины n, все элементы которого являются либо числами от 1 до n−1 (степень фиксирована), либо равны −1 (степень может быть любой). Сумма модулей элементов массива не превосходит 2n−2.

Результат

Выведите целую часть E.

Примеры

исходные данныерезультат
5
1 -1 -1 -1 -1
67
5
-1 -1 -1 -1 1
52
4
1 1 1 3
42
4
1 1 2 2
38
Автор задачи: Алексей Данилюк
Источник задачи: Петрозаводск лето 2018. t.me/umnik_team Contest
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2120. Средний вес дерева