Розподіл Дерев

Дерева є однією з найпопулярніших структур даних в інформатиці. Хоча дерева мають елегантну структуру, вони не зовсім сумісні з сучасною архітектурою комп'ютерів. У сучасних комп'ютерах пам'ять організована як одномірний масив. Оскільки дерево не є одномірною структурою, це може вплинути на ефективність кешу, коли дерево розміщується в пам'яті. Доступ до даних відбувається швидше, якщо вони вже знаходяться в кеші. Розглянемо, як можна розмістити вузли дерева для досягнення високої продуктивності кешу.

Ми визначаємо вартість розміщення дерева наступним чином. Для простоти припустимо, що пам'ять розділена на блоки, кожен з яких може вмістити не більше $B$ вузлів дерева. Коли ми звертаємося до даних у блоці, всі дані цього блоку зберігаються в кеші, і подальший доступ до даних у цьому блоці буде швидшим. Вартість доступу до вузла $u$ після вузла $v$ дорівнює $0$, якщо $u$ і $v$ знаходяться в одному блоці, і $1$ в іншому випадку. Спочатку кеш порожній, тому вартість доступу до вузла завжди дорівнює $1$. Вартість шляху v_1, v_2, \ldots, v_n є сумою вартостей, коли ми отримуємо доступ до вузлів v_1, v_2, \ldots, v_n у цьому порядку. Для дерева ми визначаємо вартість розміщення як максимальну вартість шляхів від кореневого вузла до кожного кінцевого вузла.

Нижченаведені рисунки демонструють приклади розміщення, коли B = 4 і вузол $1$ є кореневим вузлом (це відповідає дереву, описаному в третьому прикладі вхідних даних). Кожна рамка представляє блок. Лівий рисунок є прикладом розміщення з вартістю $3$. Це не оптимально, оскільки правий приклад досягає оптимальної вартості розміщення $2$.

Для даного дерева, обчисліть мінімальну вартість розміщення для кожного вузла $i$, коли цей вузол є кореневим.