# Zajęcia 03.03.2021 - problem przodka

###### tags: `Informatyka 1PR`

### Główny motyw zajęć: mamy dane drzewo i chcemy umieć odpowiadać na wiele zapytań postaci: "Czy $u$ jest przodkiem $v$?".

#### W naszych rozważaniach zakładamy, że drzewa są ukorzenione i numer wierzchołka to 1.

W pierwszej kolejności zastanówmy się, co to oznacza, że $u$ jest przodkiem $v$ (równoważnie $v$ jest potomkiem $u$):
1. $u$ jest ojcem $v$ LUB $u$ jest przodkiem ojca $v$ (powtórka z poprzedniej lekcji).
2. $u$ leży na ścieżce od korzenia do wierzchołka $v$.
3. $v$ należy do poddrzewa wierzchołka $u$.

Wszystkie z tych definicji mają bardzo ładne, intuicyjne wyjaśnienie. Pomyślmy o naszym grafie jak o drzewie genealogicznym. Korzeń możemy utożsamiać z założycielem rodziny, zatem wszystkie wierzchołki w drzewie są jego potomkami (alternatywnie, korzeń jest przodkiem wszystkich wierzchołków).
- Pierwsza definicja mówi tyle, że przodkiem $v$ jest jego ojciec, dziadek, pradziadek, prapradziadek itd., co zwija się z zwięzłą definicję rekurencyjną.
- Druga definicja mówi, że w drzewie genealogicznym $u$ jest wcześniej od $v$, a ponadto są w jedej linii od założyciela rodziny, czyli korzenia, zatem $u$ jest przodkiem $v$.
- Trzecia definicja korzysta z prostej obserwacji, że korzeń jest przodkiem wszystkich wierzchołków. Zauważmy, że $u$ jest korzeniem swojego poddrzewa, więc możemy myśleć, że jest korzeniem (założycielem) swojego poddrzewa ("podrodziny").

Pierwsza definicja daje nam pomysł na prosty, poprawny algorytm sprawdzania oczekiwanej przez nas zależności. Powiedzmy, że mamy daną tablicę `par[1..n]` (od *parent*), która dla danego wierzchołka określa numer jego ojca (tj. dla wierzchołka `v` mamy `par[v] = numer ojciec v`). Wtedy, przepisując pierwszą definicję na C++ dostajemy:

// czy u jest przodkiem v?
bool is_ancestor(int u, int v) {
	if (v == 1) 
		return false;	// 1 jest założycielem rodu, nie ma przodków
	if (par[v] == u) 		
		return true;
	return is_ancestor(u, par[v]);
}

Jest jednak pewien problem z tym rozwiązaniem. Jeżeli $N = 10^5, Q = 10^5$ (odpowiednio liczba wierzchołków oraz liczba zapytań o pary $(u, v)$), a do tego graf wygląda w ten sposób, że 1 wierzchołek połączony jest z 2, 2 z 3, 3 z 4, itd. aż 99999 połączony z 100000, a nasze zapytania składają się z samych pytań typu "czy $1$ jest przodkiem $100000$?", to algorytm będzie miał złożoność $N\cdot Q$, co zdecydowanie nie jest dla nas zadowalającym wynikiem.

### Zadanie: jak obliczać tablicę `par[1..n]`? (proste)

<!-- -->
---

Przyjrzyjmy się trzeciej definicji. Daje nam ona równoważny problem, chcemy teraz odpowiadać na pytania "czy $v$ należy do poddrzewa $u$?". W tym celu rozważmy następującą modyfikację algorytmu DFS:
:::warning
Egzekwujemy algorytm DFS w ten sam sposób co zawsze, tylko dodatkowo "trzymamy w ręce licznik", który zwiększamy odwiedzając nieodwiedzony jeszcze wierzchołek, jednocześnie przypisując tę liczbę temu wierzchołkowi.
:::

Pseudokod realizujący ten algorytm:

licznik <- 0
pre[1..n] <- 0		// tu bedziemy zapisywać to co widzimy na liczniku
vis[1..n] <- false
procedure DFS(v):
  ???
  for u in G[v]:	// pętla po sąsiadach v
    DFS(u)

Taka kolejność numeracji wierzchołków nazywa się kolejnością **preorder** (stąd nazwa tablicy). Można ją utożsamiać z czasem wejścia w odpowiednie wierzchołki.

graph G {
  node [shape=circle]
  1 -- 2
  2 -- 3
  3 -- 4
  3 -- 5
  3 -- 6
  2 -- 7
  1 -- 8
  8 -- 9
  8 -- 10
  10 -- 11
  label="Rysunek 1. Przykładowa numeracja wierzchołków w kolejności preorder."
}

Zauważmy, że zachodzi kluczowa implikacja:
:::info
## Jeśli $v$ należy do poddrzewa $u$, to jego numer preorder jest większy niż numer preorder $u$.
:::

**Jednakże implikacja odwrotna nie zachodzi!**. Widać to dobrze chociażby na powyższym rysunku: wierzchołek o numerze preorder 9 nie należy do poddrzewa wierzchołka o numerze 2, mimo tego, że jego numer jest większy.

Da się to łatwo naprawić. Analogicznie do liczenia czasu wejścia w wierzchołki możemy również liczyć czas wyjścia. Dokładniej: trzymamy drugi licznik, który zwiększamy dopiero w momencie wyjścia z wierzchołka (tj. po pętli odwiedzającej jego synów) i wtedy przypisujemy mu wartość tego licznika. Taką numerację nazywamy numeracją **postorder**.

graph G {
  node [shape=circle]
  1 [label="1, 11"]
  2 [label="2, 6"]
  3 [label="3, 5"]
  4 [label="4, 1"]
  5 [label="5, 2"]
  6 [label="6, 3"]
  7 [label="7, 4"]
  8 [label="8, 10"]
  9 [label="9, 7"]
  10 [label="10, 9"]
  11 [label="11, 8"]
  1 -- 2
  2 -- 3
  3 -- 4
  3 -- 5
  3 -- 6
  2 -- 7
  1 -- 8
  8 -- 9
  8 -- 10
  10 -- 11
  label="Rysunek 2. Numeracja wierzchołków w kolejności preorder oraz postorder."
}

Wtedy natychmiast otrzymujemy następujące twierdzenie:
:::info
Wierzchołek $u$ jest przodkiem wierzchołka $v$ wtedy i tylko wtedy, gdy preorder $v$ jest większy niż preorder $u$ oraz postorder $v$ jest mniejszy niż postorder $u$.
:::

Stąd ostateczny algorytm (mając daną już tablicę `pre[1..n]`, `post[1..n]`):

bool is_ancestor(int u, int v) {
  return pre[u] <= pre[v] && post[u] >= post[v];
}

Często zakładamy, że $u$ jest swoim własnym przodkiem, stąd `<=, >=`, a nie `<, >`.