Задача — це «найдовша зростаюча підпослідовність» на дереві. Впорядкуємо свята за днем. Друг Вуса відвідує деяку підмножину свят; якщо він побував на святі , а наступним обрав свято , то мусить встигнути переїхати:
Перше свято безкоштовне — у нульовий день можна опинитися в будь-якому місті й чекати скільки завгодно. Отже маємо класичну динаміку
а відповідь — максимум по всіх . Наївно це \mathcal{O}(m^2); заважає саме , яке не розкладається на «щось про » плюс «щось про ».
Центроїдна декомпозиція розчіплює відстань. Якщо шлях між c_i та c_j проходить через вершину , то \mathrm{dist}(c_i,c_j) = \mathrm{dist}(c_i,z) + \mathrm{dist}(z,c_j), і умова переїзду розпадається на дві незалежні частини:
Побудуємо центроїдну декомпозицію дерева. Кожне місто належить \mathcal{O}(\log n) центроїдам, і для будь-якої пари міст існує центроїд, що лежить на шляху між ними — саме там рівність точна.
Дуже зручно, що інші центроїди не зіпсують відповіді: для них
тобто умова лише суворіша за справжню. Отже жоден центроїд не дозволить неможливого переходу, а потрібний перехід дозволить точний центроїд. Тому можна спокійно брати максимум по всіх центроїдах, що містять c_j.
Реалізація. Для кожного центроїда заведемо дерево Фенвіка на максимум над стисненими значеннями ключів d + \mathrm{dist}(\cdot, z) (усі потрібні ключі відомі заздалегідь — це пари «свято, центроїд»). Обробляємо свята у порядку зростання дня і для кожного:
для всіх \mathcal{O}(\log n) центроїдів , яким належить c_j, беремо префіксний максимум у Фенвіку до порогу d_j - \mathrm{dist}(z, c_j);
— найбільше зі знайденого плюс одиниця;
у тих самих деревах оновлюємо позицію ключа 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) пам'яті.