$\renewcommand{\le}{\leqslant}$ $\renewcommand{\ge}{\geqslant}$

Puud

Sageli kohtab ülesandeid, mis on stiilis "on antud puu $N$ tipuga, arvutage selle peal blablabla". Selliste ülesannete jaoks on leiutatud palju "standardset masinavärki", mis puu struktuuri märkimisväärselt lihtustavad. Väga suur osa tõsisematest puuülesannetest kasutab lahenduse osana vähemalt üht allolevatest võtetest: Mõned vähemtähtsamad: Täna vaatame nimetatutest neid, mis on rasvases kirjas.

Puudest üldiselt

Puuks nimetatakse sidusat ja ilma tsükliteta graafi. Järgmised väited on samaväärsed:

Juurega ja juureta puud

Olgu antud $N$ tipuga puu. Sageli on otstarbekas määrata üks tippudest selle puu juureks. Sellisel juhul räägitakse juurega puust.

1 / 2
2 / 2

Kui puul on juurtipp, omavad mõtet mõisted nagu vanem ja laps ja üldisemalt eellane. Juuresoleval pildil on tipu 14 vanem märgitud punasega ja tema lapsed sinisega. Tipu 10 eellased on märgitud kollasega.

Samuti saame rääkida tipu $u$ alampuust. Tipu 6 alampuu on märgitud rohelisega.

Hoiatus: sageli kasutatakse mõistet "alampuu" ka muude puu sidusate alamgraafide kohta. Sellised alampuud ei ole ühegi tipu alampuud, aga on alampuud sellegipoolest.

Nummerdamine

DFS-järjestus

Oletame, et meil on mingi puu. Läbime selle puu sügavuti (depth-first traversal). Iga kord, kui siseneme mingisse tippu esmakordselt, paneme selle tipu numbri kirja. Koodis võiks see välja näha umbes nii:

function dfs (u):
  print(u)
  for each unvisited neighbor v of u:
    call dfs(v)

Ja visuaalselt:

1 / 41
2 / 41
3 / 41
4 / 41
5 / 41
6 / 41
7 / 41
8 / 41
9 / 41
10 / 41
11 / 41
12 / 41
13 / 41
14 / 41
15 / 41
16 / 41
17 / 41
18 / 41
19 / 41
20 / 41
21 / 41
22 / 41
23 / 41
24 / 41
25 / 41
26 / 41
27 / 41
28 / 41
29 / 41
30 / 41
31 / 41
32 / 41
33 / 41
34 / 41
35 / 41
36 / 41
37 / 41
38 / 41
39 / 41
40 / 41
41 / 41

Selle käigus me panime puu tipud mingis järjekorras kirja. Et see teekond leiti DFS (depth-first search) käigus, siis võime seda hakata kutsuma DFS-järjestuseks. Sellel järjestusel on mõned huvitavad omadused. Uurime neid.

Iga tipu alampuu teiseneb mingiks selle järjestuse lõiguks.
1 / 3
2 / 3
3 / 3

Miks see nii on? Kui DFS siseneb mingisse tippu $u$, siis käib ta kõigepealt rekursiivselt läbi $u$ lapsed, nende laste lapsed jne. Teisisõnu, ta käib tipu $u$ alampuu läbi enne, kui ta ülejäänud puud puutub. Seetõttu on selles järjestuses $u$ alampuu järjest.

On antud $N$ tipuga puu, tipud on nummerdatud $1, \ldots, N$ ja juurtipp on $1$. Küsitakse $Q$ päringut, millest igaüks on kujul $1 \le N \le 10^5, 1 \le Q \le 2 \cdot 10^5$.

Teisisõnu, peame igas päringus kontrollima, kas $v$ kuulub $u$ alampuusse. DFS-järjestuses on tipu $u$ alampuu lihtsalt üks lõik --- tähistame selle esimese positsiooni $\mathrm{enter}[u]$ ja viimase positsiooni $\mathrm{exit}[u]$. Nüüd on vastus "jah" täpselt siis, kui $\mathrm{enter}[u] \le \mathrm{enter}[v]$ ja $\mathrm{enter}[v] \le \mathrm{exit}[u]$.

Jääb veel üle arvutada iga tipu $u$ jaoks $\mathrm{enter}[u]$ ja $\mathrm{exit}[u]$. Selleks paneme sügavuti läbides kirja "ajahetke", kus iga tippu esimest korda siseneme ja viimast korda lahkume:

// idx on globaalne muutuja
function dfs (u):
  idx += 1
  enter[u] = idx
  for each unvisited neighbor v of u:
    call dfs(v)
  exit[u] = idx

Kokkuvõtteks:

  1. Teeme DFS, mis arvutab iga tipu $u$ jaoks $\mathrm{enter}[u]$ ja $\mathrm{exit}[u]$;
  2. Kui tuleb päring $u \, v$, siis kontrollime, kas $\mathrm{enter}[u] \le \mathrm{enter}[v]$ ja $\mathrm{enter}[v] \le \mathrm{exit}[u]$.
Esimese DFS tegemiseks läheb $\mathcal{O}(N)$ aega, pärast seda saab igale päringule vastata $\mathcal{O}(1)$ ajas. Keerukus on niisiis $\mathcal{O}(N + Q)$.

On antud $N$ tipuga puu, tipud on nummerdatud $1, \ldots, N$ ja juurtipp on $1$. Igasse tippu on kirjutatud üks arv; tippu $u$ kirjutatud arvu tähistame $A[u]$. Küsitakse $Q$ päringut, mis võivad olla kaht tüüpi.
  1. Antud $u$ ja $x$. Liida $A[u]$ väärtusele $x$.
  2. Antud $u$. Leia $u$ alampuus olevate arvude summa.
$1 \le N \le 10^5, 1 \le Q \le 2 \cdot 10^5$.

Asendame $B[\mathrm{enter}[u]] = A[u]$. Päringud on siis:

  1. Antud $u$ ja $x$. Liida $B[\mathrm{enter}[u]]$ väärtusele $x$.
  2. Antud $u$. Leia $B[\mathrm{enter}[u]] + B[\mathrm{enter}[u] + 1] + \cdots + B[\mathrm{exit}[u]]$.
Ehk asendades $i = \mathrm{enter}[u]$, $l = \mathrm{enter}[u]$, $r = \mathrm{exit}[u]$:
  1. Antud $i$ ja $x$. Liida $B[i]$ väärtusele $x$.
  2. Antud $l$ ja $r$. Leia $B[l] + B[l + 1] + B[l + 2] + \cdots + B[r]$.
See on Fenwicki puu tüüpülesanne. Fenwicki puuga kulub kumbagi tüüpi päringute tegemiseks $\mathcal{O}(\log N)$ aega. Kokku saame kõikidele päringutele vastata keerukusega $\mathcal{O}(N + Q \log N)$.

Madalaimad ühised eellased (LCA)

Olgu $u$ ja $v$ puus juurega 1. Nende madalaim ühine eellane $\mathrm{lca}(u, v)$ on kõige madalam ühine tipp teekondadel $u \leadsto 1$ ja $v \leadsto 1$.

Näiteks siin pildil $\mathrm{lca}(11, 16) = 7$.

On antud $N$ tipuga puu, tipud on nummerdatud $1, \ldots, N$ ja juurtipp on $1$. Vastata $Q$ päringule, millest igaüks on kujul $1 \le N \le 10^5, 1 \le Q \le 2 \cdot 10^5$.

Taaskord käime puu rekursiivselt läbi. Aga seekord prindime käesoleva tipu indeksi ka rekursiivsete kutsete vahel. Koos sellega prindime ka antud tipu kõrguse — tema kauguse juurtipust.

function dfs (u, p): // p on u vanem
  lvl[u] = lvl[p] + 1
  print(lvl[u], u)
  for each unvisited neighbor v of u:
    call dfs(v, u)
    print(lvl[u], u)
1 / 15
2 / 15
3 / 15
4 / 15
5 / 15
6 / 15
7 / 15
8 / 15
9 / 15
10 / 15
11 / 15
12 / 15
13 / 15
14 / 15
15 / 15

Oletame, et meil on vaja leida $\mathrm{lca}(u, v)$. Arvutame $\mathrm{enter}[u]$ — esimene positsioon väljatrükitud listis, kus läbisime tippu $u$. Siis $\mathrm{lca}(u, v)$ on välja trükitud listis kõige madalama kõrgusega element lõigus $[\mathrm{enter}[u], \mathrm{enter}[v]]$.

1 / 2
2 / 2

Meil on niisiis (väljatrükitud paaride) list $A$ ja meilt küsitakse päringuid "mis on kõige väikesem element $A[l], A[l + 1], \ldots, A[r]$ seas?" (siin $l = \mathrm{enter}[u]$, $r = \mathrm{enter}[v]$).

See on lõikude puu (segment tree) tüüpülesanne.

Miks on LCA oluline?

Ükski endast lugu pidav võistlus ei võtaks vastu selliseid tüüpülesandeid, nagu "leia $\mathrm{lca}(u, v)$" või "kontrolli, kas $u$ on $v$ eellane". Samas paljudes ülesannetes on mingi (võibolla palju keerulisema) lahenduse sees vaja nendele küsimustele vastata — LCAde leidmine on üks standardsetest tööriistadest puuülesannete lahendamiseks.

Miks LCAde arvutamist siis nii sageli vaja läheb? Juurega puudes saab kahe tipu vahelist teekonda väga konkreetselt kirjeldada LCAde abil.

Lühim (ja üldse ainuke, mis ei läbi ühtki tippu mitu korda) teekond $u \leadsto v$ on kujul

See tähelepanek on kasulik peaaegu igas puuülesandes, kus mingeid teekondi mainitakse. Vaatleme järgnevat võistlusülesannet (USACO 2015-2016, detsember, Platinum):

On antud puu $N$ tipuga ja $K$ erinevat paari $u \, v$; igas sellises paaris pumbatakse piima tipust $u$ läbi nendevahelise teekonna tippu $v$. Kui palju pumbatakse piima läbi tipust, kust kõige rohkem piima läbi pumbatakse? $1 \le N \le 5 \cdot 10^4$, $1 \le K \le 10^5$.

"Naiivne" lahendus on järgmine. Hoiame igas tipus meeles, kui palju piima sealt läbi pumbatakse; hakkame paare järjest läbi käima. Võtame $u$ ja $v$; käime läbi teekonna $u \leadsto v$. Liidame sellel teekonnal igale tipule 1. Lõpuks vaatame lihtsalt, mis on kõige suurem arv, mida me näeme.

1 / 6
2 / 6
3 / 6
4 / 6
5 / 6
6 / 6

Aga nii me peame $K$ korda läbi käima mingi teekonna, mis võib olla ju üsna pikk. Halvematel juhtudel on see teekond iga kord peaaegu $N$ sammu pikkune — keerukus on $\mathcal{O}(NK)$. Liiga aeglane.

Kavalam lahendus kasutab LCAsid. Hakkame paare järjest läbi käima. Võtame $u$ ja $v$; liidame tippudele $u$ ja $v$ juurde $+1$, lahutame tipust $\mathrm{lca}(u, v)$ ja tema vanemast $-1$. Kui kõik paarid on läbi käidud, siis liidame saadud arvud "alt üles" kokku.

1 / 28
2 / 28
3 / 28
4 / 28
5 / 28
6 / 28
7 / 28
8 / 28
9 / 28
10 / 28
11 / 28
12 / 28
13 / 28
14 / 28
15 / 28
16 / 28
17 / 28
18 / 28
19 / 28
20 / 28
21 / 28
22 / 28
23 / 28
24 / 28
25 / 28
26 / 28
27 / 28
28 / 28

Sellel on parem keerukus. Alguses teeme iga paari kohta $\mathcal{O}(\log N)$ tööd (meil on vaja arvutada $\mathrm{lca}(u, v)$ ja panna nelja erinevasse tippu $+1$ või $-1$). Lõpuks teeme ühe DFS, mis võtab $\mathcal{O}(N)$ aega. Keerukus kokku $\mathcal{O}(K \log N + N)$.

Kahendhüpped

$k$-s eellane

Vaatleme juurega puu tippu $u$. Nimetame:

Teisisõnu, tipu $u$ $k$-s eellane on see tipp, mis asub tipust $u$ $k$ sammu võrra "üleval".

On antud $N$ tipuga puu, tipud on nummerdatud $1, \ldots, N$ ja juurtipp on $1$. Vastata $Q$ päringule, millest igaüks on kujul $1 \le N \le 10^5, 1 \le Q \le 2 \cdot 10^5$.

Lahendusidee on järgmine. Arvutame ette iga tipu kohta, enne kui hakkame päringutele vastama:

Selleks paneme tähele, et tipu $u$ $k$-nda eellase $k$-s eellane on tema $2k$-s eellane.

// eesmärk on, et jump[u][i] oleks tipu u 2^i-s eellane
for u in 1...N:
  jump[u][0] = tipu u vanem
for k in 1...log2(N):
  for u in 1...N:
    jump[u][k] = jump[jump[u][k - 1]][k - 1]

Nüüd on meil tabel, kus iga $u$ ja $k$ kohta kirjas tipu $u$ $2^k$-s eellane. Tahame leida tipu $u$ $k$-ndat eellast. Liigume mööda neid pointereid "võimalikult suurte sammudega" üles.

function jump_up (u, k): // vaja: u k-s eellane
  for i in log2(N)...0:
    if k >= 2^i:
      u = jump[u][i]
      k -= 2^i
1 / 7
2 / 7
3 / 7
4 / 7
5 / 7
6 / 7
7 / 7

Iga päringu tegemine kulutab $\mathcal{O}(\log N)$ aega, sest meil on vaja teha kuni $\log N$ sammu üles.

Madalaimad ühised eellased (uuesti)

Madalaimaid ühiseid eellasi saab arvutada ka selliste "kahendhüpetega". Lühidalt: olgu antud tipud $u$ ja $v$. Siis:

  1. viime $u$ ja $v$ samale tasemele (nagu ülal kirjas);
  2. proovime võimalikult suurte sammudega üles minna nii, et $u$ ja $v$ ei muutuks üheks ja samaks.
  3. pärast seda on $\mathrm{lca}(u, v)$ tippude $u$ ja $v$ ühine vanem.

1 / 16
2 / 16
3 / 16
4 / 16
5 / 16
6 / 16
7 / 16
8 / 16
9 / 16
10 / 16
11 / 16
12 / 16
13 / 16
14 / 16
15 / 16
16 / 16

Väikesemast suuremasse

Rasked ja kerged servad

Olgu meil mingi juurega puu. Arvutame iga tipu kohta, mitu tippu selle alampuus on.

Igal tipul $u$ leidub üks laps $v$, mille alampuus on kõige rohkem tippe. Kui selliseid on mitu, valime suvaliselt ühe välja. Värvime iga tipu ja tema kõige suurema alampuuga lapse vahel oleva serva rasvaseks. Nii ära värvitud servi nimetame rasketeks servadeks, ülejäänud servi kergeteks servadeks.

Teekonnal mistahes tipust juurtippu on kõige rohkem $\log N$ kerget serva. Teekonnal mistahes tipust mistahes teise tippu on kõige rohkem $2 \log N$ kerget serva.

Miks nii? ...

Algoritmid väikesemast hulgast suuremasse ühendamisega

On antud juurega puu $N$ tipuga; iga tipp on värvitud mingit värvi. Leia iga tipu $u$ kohta, mitu erinevat värvi tema alampuus on. $1 \le N \le 2 \cdot 10^5$, erinevaid värve võib olla samuti kuni $2 \cdot 10^5$.