Moje rozwiązanie jest offline i działa w O((n+q) log (n+q)). Może ktoś ma prostsze podejście?

Zbudujmy sobie drzewo przedziałowe nad ciągiem modyfikacji lasu, które pozwala odpowiadać na zapytania postaci "czy wierzchołek v został pomalowany przez jakąś operację w przedziale [l;r]". Gdy mamy taką strukturę, to na zapytania możemy łatwo odpowiadać binsearchując moment przemalowania wierzchołka.

W każdym węźle drzewa trzymamy skompresowany las: zostawiamy wszystkie wierzchołki, których dotyczą operacje w przedziale, a resztę maksymalnie kontraktujemy. Zapisujemy sobie mapowanie wierzchołków pomiędzy tymi grafami. Każdy wierzchołek ojca przechodzi w dziecku na:
- wierzchołek jeśli występuje tam
- krawędź - pamiętamy wtedy też odległość w oryginalnym grafie do końców tej krawędzi
Dla każdego wierzchołka trzymamy jeszcze wartość max(promień - dystans) po kulach, które go zawierają. To wystarcza by odpowiadać na zapytania, i można robić binsearch na drzewku by mieć pojedynczy log.

Brawo Krzysiek! Bardzo fajne rozwiązanie.

Alternatywnie można odwrócić czas i zrobić link-cuta, który ma następujące operacje:
- dodaj krawędź
- usuń krawędź
- zaznacz wierzchołek - wykonane przy napotkaniu zapytania
- znajdź najbliższy zaznaczony wierzchołek i odznacz wierzchołek - wykonywane w pętli przy napotkaniu przemalowania, póki zaznaczone wierzchołki znajdują się w przemalowywanej kuli

"Może ktoś ma prostsze podejście?" - stary, masz rozwiązanie "z książki" (powiedzenie na modłę pierwszego akapitu https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK) i jeszcze się pytasz czy może ktoś ma prościej xD. Szacun

Mam do siebie żal, że nie skojarzyłem, że dynamiczną spójność offline się robi w O(n log n). Sam opisywałem parę lat temu na potyczkowym forum istotnie bardziej skomplikowaną wersję tego dla wyższych spójności https://sio2.mimuw.edu.pl/c/pa-2020-1/forum/137/1885/ w zadaniu Trzy Drogi :<. Aczkolwiek w tym zadaniu tutaj nie umiałem nawet w O(n log n) rozwiązać podproblemu "graf się nie zmienia, a wszystkie zapytania są na końcu" xd

Czy to jest rozwiązanie dla pełnego zadania? Mam problem z obsługą zapytania o dodanie/usunięcie krawędzi w tym miejscu

Tak, do pełnego. Gdy jakaś krawędź zmienia się w poddrzewie, to w grafie skompresowanym pozostawiamy jej końce, ale nie krawędź. Gdy liczymy mapowanie z ojca do dziecka, bierzemy graf z ojca + krawędzie, które stały się w nim "finalne" (tzn. nie zmieniają się w nim, tylko w drugim dziecku ojca). Taki graf kompresujemy i dla każdego wierzchołka usuniętego wyliczamy dystans do dwóch najbliższych w skompresowanym grafie.

W liściach, które odpowiadają kulom, grafy są jednowierzchołkowe - wpisujemy po prostu tam promień kuli. Gdy wracamy do góry drzewa, przepisujemy promienie wierzchołków z pod spodu, i uzupełniamy promienie dla pozostałych wierzchołków wg obliczonych dystansów.