Коли місто блокує подорож. Мандрівник клану виходить з в момент і йде шляхом до . У місто він приходить у момент T + \mathrm{dist}(u, w), тож його не пропустить тоді й лише тоді, коли
Відповідь — перше таке місто на шляху (або «пройде», якщо таких немає).
Позбуваємось відстані в умові. Шлях розпадається на підйом u \to \mathrm{LCA} і спуск \mathrm{LCA} \to v. Позначимо D_x — відстань від кореня до .
Для верхньої половини \mathrm{dist}(u,w) = D_u - D_w, і умова перетворюється на
Для нижньої половини \mathrm{dist}(u,w) = D_u + D_w - 2 D_{\mathrm{LCA}}, тобто
Головне, що в обох випадках ліворуч стоїть величина, що залежить лише від міста, а праворуч — константа запиту. Заведемо два ключі:
Як обійти умову a_w \ne b. Якби не клани, вистачило б звичайного мінімуму ключа на вертикальному відрізку. Клан заважає: мінімум може досягатися саме на «своєму» місті, яке пропускає.
Рятує стандартний прийом: у кожному вузлі двійкових підйомів зберігаємо два найменші ключі з різними кланами. Тоді для будь-якого забороненого клану хоча б один із двох кандидатів має a \ne b — і це саме мінімум серед «чужих» міст. Злиття двох таких пар при побудові таблиці робиться вручну: об'єднуємо чотири кандидати, для однакових кланів лишаємо менший ключ, і беремо два найкращі з різними кланами.
Отже будуємо дві таблиці двійкових підйомів (окремо для \mathrm{key}^{\uparrow} і \mathrm{key}^{\downarrow}), у кожній комірці — батько через 2^j кроків, сумарна довжина та описана пара кандидатів.
Пошук першого міста. Верхня половина: йдемо від вгору й на кожному кроці перевіряємо, чи є в блоці з 2^j предків «чуже» місто з ключем \le T + D_u. Якщо немає — стрибаємо, якщо є — зменшуємо крок. Так за \mathcal{O}(\log n) спускаємось до першого міста, що блокує; це і є відповідь.
Нижня половина обробляється так само, але шукати треба місто, найближче до , тобто найвище на відрізку [\mathrm{LCA}, v]. Зручно робити двійковий пошук за глибиною: для кандидата агрегат на ділянці предків від глибини до глибини дістаємо тими самими підйомами. Разом — \mathcal{O}(\log^2 n) на запит (або \mathcal{O}(\log n) при акуратнішому спуску).
Не забудьте перевірити саме місто (мандрівник стоїть у ньому в момент ) і місто , а також випадок, коли сам блокує шлях — він належить обом половинам, тож зручно віднести його до однієї з них і не рахувати двічі.
Складність — \mathcal{O}\bigl((n + m)\log n\bigr) пам'яті та \mathcal{O}(n \log n + m \log^2 n) часу. Відстані до 10^3 \cdot 10^5 = 10^8, а часи до 10^9, тож t_w + D_w ще вміщується в біти, але надійніше рахувати у -бітних.