zadania Randka OI

Question

Uczę się o LCA i natknąłem się na takie zadanie: link ,które rzekomo da się zrobić za pomocą LCA. Przybruciłem jakiegoś DFS-a / BFS-a na 40pkt, no i to wsm tyle co mu się udało wymyśleć. Kompletnie nie widzę jak zrobić szybciej. Nie widzę też jak skorzystać z LCA w tym zadaniu, chociaż max / min na ścieżce jest charakterystyczny dla tych jump pointerów. Poprosiłbym o hinta.

Z góry dzięki. 

Answer 1

Graf w którym z każdego wierzchołka wychodzi dokładnie jedna krawędź ma ciekawe własności. Jakie?

Comments

Można go podzielić na drzewa tak jak w tym zadaniu skarbonki z OI i już wsm coraz bliżej do LCA.

---

Tak, ta obserwacja wystarczy do rozwiązania zadania

---

Tak faktycznie jest to prawda. Nie wiem czemu wtedy nie umiałem tego zrobić, ale faktycznie dzielimy ten nasz graf strzałkowy na takie właśnie cykle, do każdego mogą wchodzić jakieś krawędzie i powstają nam takie tak jakby drzewa i jump pointerami sprawdzamy czy da się dojść z a do b / do cyklu, jak do cyklu to tam wzorkiem na cyklu liczymy wynik. I wchodzi na 100pkt.