Стажировка ML — Tree Barber: минимальная сумма энтропий после стрижки

Условие

Дано бинарное дерево решений (классификатор) на 2n - 1 узлах: n листьев, остальные — внутренние. Каждый лист помечен меткой 0 или 1 (бинарная классификация). Внутренние узлы — точки разбиения.

Для каждой вершины v определена стоимость стрижки = энтропия Шеннона меток в поддереве, нормированная на мощность поддерева:

H(v) = -p log p - (1 - p) log (1 - p)

где p — доля единиц в листьях поддерева v. Если p ∈ {0, 1}, то H = 0.

«Стричь» дерево = выбрать поддерево и заменить его на лист с большинством голосов. Минимально возможное число листьев после стрижки — 1 (стричь всё), либо оставить как есть.

Найти набор поддеревьев для стрижки (необязательно вложенных), минимизирующий сумму энтропий стрижек.

Формат ввода

n                    # 1 ≤ n ≤ 300
n - 1 чисел           # для внутренних узлов 1..n-1: индекс родителя
n чисел y_1..y_n     # метки листьев, y_i ∈ {0, 1}

Гарантируется, что:

• листья имеют номера от n до 2n − 1;
• каждый внутренний узел имеет двух детей;
• 1 ≤ p_i < i (родитель меньше по индексу).

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

Минимальная сумма энтропий после оптимальной стрижки. Точность 10^-6.

Примеры

Пример 1. n=2, дерево: один корень с двумя листьями 0, 1. Если стрижём весь корень — энтропия H(1/2) = ln 2 ≈ 0.693. Вывод: 0.6931471806.

Пример 2. n=5, дерево с метками 0, 0, 1, 1, 1 так, что есть полностью чистые поддеревья. Вывод: 0.

Пример 3. n=4, метки 0, 1, 1, 0. Вывод: 1.3862943611 (= 2 ln 2).