Архівне дерево#13102

Архівне дерево (Розбір)

Підвісимо дерево за і запишемо f_v = k_v \cdot f_p для кожної папки v \ne s з батьківською папкою . Тоді f_v — добуток множників на шляху від до , а дві підпапки однієї папки мають різні назви тоді й лише тоді, коли в них різні множники, бо f_p у них спільне. Якщо помножити всі назви в піддереві на одне й те саме число, піддерево лишиться коректним, тож піддерева можна оптимізувати незалежно. Нехай — найменша можлива найбільша назва в піддереві , якщо f_u = 1; тоді h(\text{листок}) = 1, а відповідь дорівнює . Якщо підпапка папки отримує множник k_c, то найкраще, чого може досягти її піддерево, — це k_c \cdot h(c).

Ключове твердження. Нехай g_1 \ge g_2 \ge \ldots \ge g_m — значення для m \ge 1 підпапок папки . Тоді

h(u) = \max_{1 \le i \le m} i \cdot g_i,

тобто підпапка з -м за величиною значенням отримує множник .

Доведення. По-перше, досить множників 1, 2, \ldots, m: -те найменше з попарно різних додатних цілих чисел не менше за , тож заміна його на зберігає попарну різність множників і не збільшує жодного добутку. По-друге, більше значення має отримати менший множник. Якщо g \ge g' і a < b, то

\max(a g,\, b g') \le b g \le \max(b g,\, a g'),

тож обмін множниками двох підпапок з g \ge g', які отримали b > a, ніколи не збільшує максимуму (аргумент обміну). Після всіх таких обмінів множники 1, \ldots, m дістаються підпапкам у порядку спадання .

Значення лишаються малими: i \cdot g_i \le g_1 + \ldots + g_i, тож за індукцією ніколи не перевищує розміру піддерева . Відповідь не більша за , хоча це добуток багатьох множників, і 32-бітних цілих досить.

Алгоритм. Запустимо BFS з , щоб знайти батьківські папки, а потім оброблятимемо папки у зворотному порядку BFS: зберемо значення підпапок, відсортуємо їх за спаданням і візьмемо \max_i i \cdot g_i. Кожна папка сортується один раз як підпапка, тож сортування загалом коштує O(n \log n).

Складність — O(n \log n) на тестовий випадок.