Поїздка на автомобілі#520

Поїздка на автомобілі (Розбір)

Що це за граф. Зв'язний граф із вершин і рівно ребер має рівно один цикл: це «кактус-сонечко» — цикл, до якого підвішені дерева. Ця обставина й робить задачу розв'язною.

Три спостереження.

1. Об'їзди не допомагають. Заправитися можна в будь-якій вершині, тож найкращий можливий стан у вершині — повний бак, і жодне блукання цього не покращить. Отже достатньо розглядати прості шляхи з у . А в графі з одним циклом таких шляхів щонайбільше два — «в обхід циклу зліва» і «справа».

2. Ребра, важчі за бак, непрохідні. Якщо на шляху є ребро з w > V, цей маршрут неможливий; якщо обидва маршрути такі — відповідь .

3. Уздовж фіксованого шляху оптимальна жадібність. Їдемо, доки палива вистачає на наступне ребро; щойно не вистачає — заправляємось. Заправлятися раніше немає сенсу: бак усе одно наповнюється до , тож рання заправка не дає більше палива пізніше, а лічильник збільшує. Формально це стандартний обмін: будь-який розв'язок можна посунути до жадібного, не збільшивши кількості заправок.

Зводимо до дерева. Приберемо одне ребро циклу — лишиться дерево. Тоді:

  • перший маршрут — звичайний шлях по дереву від до ;

  • другий — шлях s \to u, прибране ребро , шлях v \to t.

Відповідь — мінімум із двох (кожен рахуємо, лише якщо всі його ребра не важчі за ).

Швидка жадібність на шляху дерева. Шлях s \to t розпадається на підйом до найближчого спільного предка й спуск до .

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

Спуск. Тут напрямок протилежний, тому ті самі вказівники не годяться. Розкладемо дерево важко-легкою декомпозицією: спуск від спільного предка до проходить \mathcal{O}(\log n) важких ланцюжків, а всередині ланцюжка вершини лежать поспіль у масиві — там знову працює двійковий підйом, побудований для цього ланцюжка. Разом — \mathcal{O}(\log^2 n) на запит.

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

Складність — \mathcal{O}\bigl((n + q)\log^2 n\bigr). Ваги до 10^9, а суми вздовж шляху — до 2\cdot10^{14}, тож усі відстані в -бітних.