Zadanie o drzewie – opis rozwiązania

Autor: Maciej Mączka

Link do “Zadania o drzewie”:
https://szkopul.edu.pl/problemset/problem/RadMmqx9FS_Wjr0uu881I8o9/site
Zadanie pochodzi z konkursu “Oki Wakacje 2025”
https://oki.org.pl/wakacyjny-konkurs-programistyczny/
Dołączenie do konkursu:
https://szkopul.edu.pl/c/oki-wakacje-2025/join/KzdeoNRsk8ZTclg7739upjmo/

Poniższy wspaniały edytorial autora – Maćka Mączki – prowadzi nas stopniowo od rozwiązania brutalnego do kluczowych obserwacji i rozwiązania optymalnego.
Serdeczne ukłony dla Maćka za super zadanie i samouczek!

–

Zadanie o drzewie – editorial

 

Przy wszystkich analizach złożoności przyjmujemy n = q.

---

1. Rozwiązanie brutalne — O(n2)

Dla każdego zapytania typu 3 x uruchamiamy z wierzchołka x algorytm BFS i „brutalnie” wyliczamy odpowiedź.

---

2. Rozwiązanie pierwiastkowe — O(n log n + n√n)

1. Stosujemy klasyczną dekompozycję pierwiastkową po zapytaniach: dzielimy je na bloki długości B = ⌈√q⌉.
2. Musimy obsłużyć:
   • aktualizację (co B zapytania),
   • pytania typu 3 x.
3. Aktualizacja bloku:
   1. Przechodzimy po B zapytaniach i zapisujemy wierzchołki aktywne przez cały blok.
   2. Z nich odpalamy BFS „z wielu źródeł naraz” i zapamiętujemy dystans do każdego wierzchołka.
4. W trakcie obróbki kolejnych zapytań trzymamy zbiór Z „świeżo” włączonych wierzchołków
   (|Z| < O(B)). Dla zapytania 3 x bierzemy minimum z:
   • dystansu wstępnie (pre-)przetworzonego oraz
   • dystansów do wszystkich wierzchołków Z (obliczanych O(1) przez LCA na sparse-table).

Łączna złożoność: O(n log n + n√n).

---

3. Rozwiązanie wzorcowe — O(n log2 n)

3.1 Podzadanie 1 (tylko x = 1 w pytaniach 3)

Trzymamy kolejkę priorytetową pq z parami (dystans, wierzchołek).
Operator < gwarantuje, że pq.top() zwraca:

1. najmniejszy dystans,
2. w razie remisu – najniższy numer wierzchołka.

// wstępny BFS od 1
pq.push({dist(x,1), x});
active[x] = true;     // tablica aktywności

// zapytanie 1 x
pq.push({dist(x,1), x});
active[x] = true;

// zapytanie 2 x
active[x] = false;

// zapytanie 3 (x==1)
while (!pq.empty() && !active[pq.top().second]) pq.pop();
if (pq.empty())
    cout << "WERE LOOSING!\n";
else
    cout << pq.top().first << " " << pq.top().second << '\n';

W zapytaniu 3 wykorzystujemy klasyczną technikę lazy pop (czyszczenie nie-aktywnych elementów z góry pq).

3.2 Pełne rozwiązanie — drzewo centroidowe

Rozbijamy drzewo poprzez dekompozycję centroidową. Dla każdego centroidu przechowujemy kolejkę pq z aktywnymi wierzchołkami w jego poddrzewie centroidowym wraz z dystansem w drzewie oryginalnym (!!!).

int build_centroid(int v) {
    int ctr = find_centroid(v);
    is_off[ctr] = true;          // „wycinamy” centroid
    for (int u : g[ctr])
        if (!is_off[u])
            centroid_tree[ctr].push_back(build_centroid(u));
    return ctr;
}

Fakty:

• Głębokość drzewa centroidowego ≤ ⌈log n⌉.
• Każdy wierzchołek ma ≤ log n centroidowych przodków, więc całkowity preprocessing dystansów to O(n log n).

Obsługa zapytań

1. 1 x: idziemy po centroid-parentach x i dodajemy x do odpowiednich kolejek pq.
2. 2 x: analogicznie usuwamy (oznaczamy active[x]=false).
3. 3 x:

   pair<int,int> ans = {INF, INF};
   int z = x;
   while (z) {
       while (!pq[z].empty() && !active[pq[z].top().second]) pq[z].pop();
       ans = min(ans, pq[z].empty() ? make_pair(INF,INF) : pq[z].top());
       z = centroid_parent[z];
   }
   if (ans.first == INF)
       cout << "WERE LOOSING\n";
   else
       cout << ans.first << " " << ans.second << '\n';
   

Poprawność (szkic dowodu nie-wprost)

Zakładamy, że istnieje włączony wierzchołek Y będący prawidłową odpowiedzią, a algorytm wypisał inny W.
Z — najniższy centroid-parent x, którego poddrzewo zawiera Y. Wtedy lca(x,Y)=Z także w drzewie oryginalnym.
Porównując dist(x,Y) i dist(x,W) (podział odległości przez Z, L) otrzymujemy sprzeczność z założeniem minimalności pq[Z].top(). ∎

Złożoność czasowa: O(n log2 n)
Złożoność pamięciowa: O(n log n)

---

© 2025 Maciej Mączka · Maciek życzy Ci wielu obserwacji! 😊