Najniższy wspólny przodek
Drzewo to graf nieskierowany, w którym dowolne dwa wierzchołki są połączone dokładnie jedną prostą ścieżką. Innymi słowy, każdy połączony wykres bez cykli jest drzewem. – Wikipedia
Najniższy wspólny przodek (LCA) to pojęcie w teorii grafów i informatyce. Niech T będzie zakorzenionym drzewem z N węzłami. Najniższy wspólny przodek jest zdefiniowany między dwoma węzłami v i w jako najniższy węzeł w T, który ma zarówno v, jak i w jako potomków (gdzie pozwalamy, aby węzeł był potomkiem samego siebie). – Wikipedia
Twoim zadaniem w tym zadaniu jest znalezienie LCA dowolnych dwóch danych węzłów v i w w danym drzewie T.
Na przykład LCA węzłów 9 i 12 w tym drzewie to numer węzła 3.
Wejście
Pierwszy wiersz danych wejściowych będzie liczbą przypadków testowych. Każdy przypadek testowy rozpocznie się od liczby N oznaczającej liczbę węzłów w drzewie, 1 <= N <= 1000. Węzły są ponumerowane od 1 do N. Każdy następny N wierszy będzie zaczynał się od liczby M oznaczającej liczbę węzłów potomnych N-tego węzła, 0 <= M <= 999, po której następuje M liczb węzłów potomnych N-tego węzła. Następny wiersz będzie liczbą Q liczba zapytań, na które musisz odpowiedzieć dla danego drzewa T, 1 <= Q <= 1000. Każdy następny wiersz Q będzie miał dwie liczby v i w, w których musisz znaleźć LCA v i w w T, 1 <= v, w <= 1000.
Dane wejściowe zagwarantują, że istnieje tylko jeden korzeń i brak cykli.
Wyjście
Dla każdego przypadku testowego wypisz Q + 1 wiersze, Pierwszy wiersz będzie miał „Przypadek C:” bez cudzysłowów, gdzie C jest numerem przypadku zaczynającym się od 1. Kolejne Q wiersze powinny być LCA odpowiednio dla podanych v i w.
Przykład
Wejście
1 7 3 2 3 4 0 3 5 6 7 0 0 0 0 2 5 7 2 7
Wyjście
Case 1: 3 1
Zadanie jest tłumaczeniem zadania LCA – Lowest Common Ancestor. Źródło: https://www.spoj.com/problems/LCA/
Autor zadania: https://www.spoj.com/users/hossamyosef/
Kluczem do poprawnego rozwiązania zadania jest jego przeczytanie i zrozumienie a także sprawdzenie specyfikacji wejścia i wyjścia. Należy uważać na wypisanie danych – przed kazdym wpisaniem należy dodać „CASE” oraz numer.
Przykład:
1 8 3 2 3 4 0 3 5 6 7 0 0 0 1 8 0
Po wczytaniu danych uzyskujemy takie drzewo:
Problem znajdowania najmniejszego wspólnego przodka można sprowadzić do problemu znajdowania minimum w przedziale. Wykonujemy pre processing w celu tworząc tablice zawierającą:
- I – kolejność odwiedzin na ścieżce
- V – numer wierzchołka
- H – odległość względem korzenia
Podkreślone wierzchołki oznaczają pierwsze wystąpienie danego wierzchołka.
W ten sposób uzyskana tablica pozwala odczytać z danego zakresu węzeł o najniższej odległości od korzenia. Mins ma przechowywać dla danego zakresu najbardziej odległy koncieczny wierzchołek dla liczba z końca tego zakresu.
Przykład
2 6 5 7
Zapytanie o najniższy węzeł pomiędzy drugim i szóstym wierzchołkiem:
Przykład zapytania pomiędzy piątym i siódmym wierzchołkiem:
Kod źródłowy w C++:
#include <bits/stdc++.h> using namespace std; vector<int> first; vector<pair<int, int>> path; vector<vector<int>> edges; vector<vector<pair<int, int>>> mins; int query(int L, int R) { int left = first[L]; int right = first[R]; if (left > right) swap(left, right); int length = right - left + 1; int k = (int) log2(length); return min(mins[left][k], mins[right - (1 << k) + 1][k]).second; } void dfs(int u, int H) { first[u] = path.size(); path.push_back({H, u}); for (auto v: edges[u]) { dfs(v, H + 1); path.push_back({H, u}); } } int main() { int tests; cin >> tests; for (int i = 0; i < tests; i++) { int n; cin >> n; first.assign(n + 1, 0); edges.assign(n + 1, vector<int>()); path.clear(); vector<int> root(n + 1, 0); for (int j = 1; j <= n; j++) { int number; cin >> number; for (int k = 0; k < number; k++) { int vertice; cin >> vertice; root[vertice] = 1; edges[j].push_back(vertice); } } int trueRoot = 0; for (int j = 1; j <= n; j++) { if (root[j] == 0) trueRoot = j; } assert(1 <= trueRoot && trueRoot <= n); dfs(trueRoot, 0); int M = path.size(); int logM = (int) log2(M); mins.assign(M, vector<pair<int, int>> (1 + logM)); for (int j = 0; j < M; j++) { mins[j][0] = path[j]; } for (int j = 1; j <= logM; j++) { for (int k = 0; k + (1 << j) <= M; k++) { mins[k][j] = min(mins[k][j - 1], mins[k + (1 << (j - 1))][j - 1]); } } int q; cin >> q; vector<int> result; for (int j = 0; j < q; j++) { int L, R; cin >> L >> R; result.push_back(query(L, R)); } cout << "Case " << i + 1 << ":" << endl; for(int j = 0; j< result.size(); j++){ cout << result[j] << endl; } } return 0; }