“Zadanie o drzewie” – Omówienie zadania

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(n²)

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 log² n)

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

Trzymamy kolejkę priorytetową pq z parami (dystans, wierzchołek).
Operator < gwarantuje, iż 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 wszystkich 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, iż 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 log² n)
Złożoność pamięciowa: O(n log n)

---

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