n узлов с номерами от 0 до n - 1 устроена как двоичное дерево с корнем в узле 0: у каждого узла не больше двух подчинённых. Дан массив boss, где boss[i] — родитель узла i, а boss[0] = -1.
Оценка узла считается так: уберите этот узел вместе со всеми его связями. Сеть распадётся на одну или несколько непустых частей; оценка — произведение размеров этих частей (размер — число узлов в части).
Верните, сколько узлов имеют максимальную оценку.boss=[-1, 0, 1, 1, 0] → 3
Без узла 0 остаются части размером 3 и 1: оценка 3. Без узла 1 — части 1, 1 и 2: оценка 2. Без любого из листьев 2, 3, 4 остаётся одна часть из 4 узлов: оценка 4. Максимум 4 у трёх узлов.
boss=[-1, 0] → 2
Без любого из двух узлов остаётся один узел, у обоих оценка 1.
boss=[-1, 0, 1, 2, 3] → 3
Цепочка из 5 узлов. Без крайнего узла 0 или 4 остаётся часть из 4 узлов, без среднего узла 2 — две части по 2. У всех трёх оценка 4, а у узлов 1 и 3 — только 1 · 3 = 3.
n = len(boss) ≤ 10⁵boss[0] = -1, для i ≠ 0: 0 ≤ boss[i] ≤ n - 1boss задаёт корректное двоичное деревоboss=[-1, 0, 1, 1, 0]
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 55 тестов на сервере, включая скрытые.