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:
- dünaamiline planeerimine (puu peal) (dynamic programming);
- tippude kavalad ümbernummerdamised;
- kahendhüpped binary lifting;
- väikesemast suuremasse ühendamine (merging small to large);
- raske-kerge tükeldus (heavy-light decomposition);
- tsentroidipuu (centroid tree, centroid decomposition);
Mõned vähemtähtsamad:
- erinevad ruutjuurelised tükeldused (square-root decomposition);
- Prüferi jadad (Prüfer sequence);
Täna vaatame nimetatutest neid, mis on rasvases kirjas.
1. Puudest üldiselt
Puuks nimetatakse sidusat ja ilma tsükliteta graafi. Järgmised väited on samaväärsed:
- \(N\) tipuga graaf on puu;
- \(N\) tipuga graaf on sidus ja tsükliteta;
- \(N\) tipuga graaf on sidus ja \(N - 1\) servaga;
- \(N\) tipuga graaf on \(N - 1\) servaga ja tsükliteta;
- \(N\) tipuga graafis on iga kahe tipu vahel täpselt üks teekond (mis ei läbi ühtki tippu mitu korda).
1.1. 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.
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.
Hoiatus: sageli kasutatakse mõistet "alampuu" ka muude puu sidusate alamgraafide kohta. Sellised alampuud ei ole ühegi tipu alampuud, aga on alampuud sellegipoolest.
2. Nummerdamine
2.1. 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(u)
Ja visuaalselt:
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.
Tähelepanek. Iga tipu alampuu teiseneb mingiks selle järjestuse lõiguks.
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.
Ülesanne. 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
- Antud \(u\) ja \(v\). Kontrollida, kas \(u\) on \(v\) eellane.
\(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:
- Teeme DFS, mis arvutab iga tipu \(u\) jaoks \(\mathrm{enter}[u]\) ja \(\mathrm{exit}[u]\);
- 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)\).
Ülesanne. 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.
- Antud \(u\) ja \(x\). Liida \(A[u]\) väärtusele \(x\).
- 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:
- Antud \(u\) ja \(x\). Liida \(B[\mathrm{enter}[u]]\) väärtusele \(x\).
- 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]\):
- Antud \(i\) ja \(x\). Liida \(B[i]\) väärtusele \(x\).
- 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)\).
2.2. 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\).
Ülesanne. On antud \(N\) tipuga puu, tipud on nummerdatud \(1, \ldots, N\) ja juurtipp on \(1\). Vastata \(Q\) päringule, millest igaüks on kujul
- Antud \(u\) ja \(v\). Leia \(\mathrm{lca}(u, v)\).
\(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)
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]]\).
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.
2.3. 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.
Tähelepanek. Lühim (ja üldse ainuke, mis ei läbi ühtki tippu mitu korda) teekond \(u \leadsto v\) on kujul
- mõned sammud "üles" \(u \leadsto \mathrm{lca}(u, v)\);
- mõned sammud "alla" \(\mathrm{lca}(u, v) \leadsto v\).
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.
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.
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)\).
3. Kahendhüpped
3.1. \(k\)-s eellane
Vaatleme juurega puu tippu \(u\). Nimetame:
- tema esimeseks eellaseks tema vanemat;
- tema teiseks eellaseks tema vanema vanemat;
- tema kolmandaks eellaseks tema vanema vanema vanemat;
- jne.
Teisisõnu, tipu \(u\) \(k\)-s eellane on see tipp, mis asub tipust \(u\) \(k\) sammu võrra "üleval".
Ülesanne. On antud \(N\) tipuga puu, tipud on nummerdatud \(1, \ldots, N\) ja juurtipp on \(1\). Vastata \(Q\) päringule, millest igaüks on kujul
- Antud \(u\) ja \(k\). Leia tipu \(u\) \(k\)-s eellane.
\(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:
- tema esimese eellase;
- tema teise eellase;
- tema neljanda eellase;
- tema kaheksanda eellase;
- tema kuueteistkümnenda eellase;
- jne.
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
Iga päringu tegemine kulutab \(\mathcal{O}(\log N)\) aega, sest meil on vaja teha kuni \(\log N\) sammu üles.
3.2. Madalaimad ühised eellased (uuesti)
Madalaimaid ühiseid eellasi saab arvutada ka selliste "kahendhüpetega". Lühidalt: olgu antud tipud \(u\) ja \(v\). Siis:
- viime \(u\) ja \(v\) samale tasemele (nagu ülal kirjas);
- proovime võimalikult suurte sammudega üles minna nii, et \(u\) ja \(v\) ei muutuks üheks ja samaks.
- pärast seda on \(\mathrm{lca}(u, v)\) tippude \(u\) ja \(v❯\) ühine vanem.
4. Väikesemast suuremasse
4.1. 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.
Tähelepanek. 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? ...
4.2. Algoritmid väikesemast hulgast suuremasse ühendamisega
Ülesanne. 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\).