Козак Вус і свята#136

Козак Вус і свята (Editorial)

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

d_j - d_i \;\ge\; \mathrm{dist}(c_i, c_j).

Перше свято безкоштовне — у нульовий день можна опинитися в будь-якому місті й чекати скільки завгодно. Отже маємо класичну динаміку

\mathrm{dp}[j] \;=\; 1 + \max\bigl\{\, \mathrm{dp}[i] \ :\ d_i + \mathrm{dist}(c_i, c_j) \le d_j \,\bigr\},

а відповідь — максимум по всіх . Наївно це \mathcal{O}(m^2); заважає саме , яке не розкладається на «щось про » плюс «щось про ».

Центроїдна декомпозиція розчіплює відстань. Якщо шлях між c_i та c_j проходить через вершину , то \mathrm{dist}(c_i,c_j) = \mathrm{dist}(c_i,z) + \mathrm{dist}(z,c_j), і умова переїзду розпадається на дві незалежні частини:

\underbrace{d_i + \mathrm{dist}(c_i, z)}_{\text{ключ свята } i} \;\le\; \underbrace{d_j - \mathrm{dist}(z, c_j)}_{\text{поріг свята } j}.

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

Дуже зручно, що інші центроїди не зіпсують відповіді: для них

\mathrm{dist}(c_i, z) + \mathrm{dist}(z, c_j) \;\ge\; \mathrm{dist}(c_i, c_j),

тобто умова лише суворіша за справжню. Отже жоден центроїд не дозволить неможливого переходу, а потрібний перехід дозволить точний центроїд. Тому можна спокійно брати максимум по всіх центроїдах, що містять c_j.

Реалізація. Для кожного центроїда заведемо дерево Фенвіка на максимум над стисненими значеннями ключів d + \mathrm{dist}(\cdot, z) (усі потрібні ключі відомі заздалегідь — це пари «свято, центроїд»). Обробляємо свята у порядку зростання дня і для кожного:

  1. для всіх \mathcal{O}(\log n) центроїдів , яким належить c_j, беремо префіксний максимум у Фенвіку до порогу d_j - \mathrm{dist}(z, c_j);

  2. — найбільше зі знайденого плюс одиниця;

  3. у тих самих деревах оновлюємо позицію ключа d_j + \mathrm{dist}(z, c_j) значенням .

Свята з однаковим днем коректно опрацьовуються тим самим кодом: різниця днів нульова, тож перехід дозволений лише в межах одного міста (нульова відстань), як і має бути.

Відстані до центроїда рахуються обходом його компоненти під час побудови декомпозиції; довжини доріг до 10^9, а днів до 10^{18} — усе в -бітних типах.

Складність — \mathcal{O}\bigl((n + m)\log^2 n\bigr) часу і \mathcal{O}\bigl((n+m)\log n\bigr) пам'яті.