Tree Subsets#529

Tree Subsets (Editorial)

Крок 1: перейдемо до доповнення. Умова «якщо v \in S, то все піддерево теж у » означає, що замкнена вниз. Тоді доповнення T = V \setminus S замкнене вгору: разом із вершиною воно містить її батька. Іншими словами,

— це зв'язне піддерево, що містить корінь (або порожня множина).

Розміри пов'язані як |T| = n - k, а значення — як \operatorname{xor}(S) = \operatorname{xor}(\text{все дерево}) \oplus \operatorname{xor}(T). Тому далі працюємо зі звичними «кореневими зв'язними піддеревами», що набагато зручніше.

До речі, звідси одразу видно, що множина будь-якого розміру існує завжди: з повного дерева можна по одному прибирати листки, щоразу зменшуючи розмір на одиницю й зберігаючи замкненість. Тому відповідь ніколи не буває «немає».

Крок 2: динаміка на дереві. Для вершини зберігаємо масив X_v довжини \mathrm{sz}(v) + 1: для кожного розміру — які парності досяжні. Значень усього три: «лише », «лише », «обидві». Об'єднання дітей — це згортка за розміром із XOR парностей, а потім додаємо саму вершину (зсув на одиницю й XOR з a_v) і не забуваємо варіант «порожньо».

Наївно згортка коштує добуток довжин, тобто \mathcal{O}(n^2) разом. Потрібні два спостереження.

Спостереження 1: коли виникає «обидві». Нехай зливаємо та , і в позиції вікно пар — це X[i] \oplus Y[s-i]. Якщо хоч один задіяний елемент уже «обидві», результат теж «обидві». Інакше всі елементи однозначні, і результат однозначний тоді й лише тоді, коли функція i \mapsto X[i] \oplus Y[s-i] стала — тобто коли вікно масиву дослівно збігається з перевернутим або з його побітовим доповненням.

А це вже класична задача про порівняння рядка зі зсувом: беремо поліноміальні хеші , перевернутого та доповнення перевернутого і за на позицію перевіряємо збіг вікна. (Хеш варто брати подвійний — за двома модулями; ймовірність колізії на 4\cdot10^5 порівнянь інакше не така вже й мала.)

Спостереження 2: чому це швидко. Значення в позиції може лише перейти з однозначного в «обидві» — назад не повертається. Тому зберігатимемо позиції з однозначними значеннями в упорядкованій множині й під час злиття пропускатимемо позиції, уже позначені як «обидві»: перехід по множині коштує логарифм, а кожна позиція змінює стан щонайбільше один раз за весь час роботи. Разом із класичним прийомом «зливаємо менше в більше» це дає близьку до лінійної складність замість квадратичної.

Крок 3: відповідь. Наприкінці маємо масив по розмірах ; переносимо його на k = n - |T| і XOR-имо з парністю всього дерева. Виводимо , або за правилом з умови.

Складність — \mathcal{O}(n \log n) на тест, сумарно по всіх тестах теж \mathcal{O}(n \log n). Уся структура тримається на тому, що значень лише три, — саме тому масиви можна порівнювати хешами, а не перебирати попарно.