1. podúloha

V tejto podúlohe tvorí celý strom jednu cestu. Môžeme si teda vrcholy predstaviť usporiadané zľava doprava a postupne nimi prechádzať.

Keďže každý zo špeciálnych vrcholov musí patriť do práve jednej zásobovacej cesty, počas prechodu si stačí pamätať 2 veci:

• Či sa práve nachádzame na zásobovacej ceste.
• Aká je celková dĺžka ciest.

Na začiatku sme mimo cesty. Keď prídeme do špeciálneho vrcholu, musíme začať novú cestu alebo ukončiť práve prebiehajúcu cestu. Ak sa po prechode do ďalšieho vrcholu nachádzame na aktívnej ceste, hrana medzi týmito dvoma vrcholmi patrí do riešenia a teda pripočítame 1 k celkovej dĺžke ciest. Takto postupne prejdeme celý strom.

Výsledkom je počet hrán, ktoré ležia medzi prvým a druhým špeciálnym vrcholom, medzi tretím a štvrtým atď.

2. podúloha

V tejto podúlohe platí $2k = n$, teda každý vrchol stromu je špeciálny.

Ak by nejaká zásobovacia cesta mala aspoň 2 hrany, obsahovala by aj nejaký vnútorný vrchol. Keďže všetky vrcholy sú špeciálne, tento vrchol by bol tiež špeciálny, a preto by musel byť koncom svojej vlastnej zásobovacej cesty čo by v tomto prípade nebol. Preto musí mať každá zásobovacia cesta práve jednu hranu.

Z toho vieme vydudekovať, že v skutočnosti hľadáme úplné párenie stromu a to sa dá spraviť greedy jedným DFS prechodom.

To či sa to dá teda vieme zistiť tak, že najprv vojdeme DFS-kom do listov. Tie nemôžu byť spárené s ničím iným než ich rodičom a teda ich spárime. Následne keď budeme stúpať po strome a narazíme na nespárený vrchol, tiež ho spárime s jeho rodičom. Takto prejdeme celý strom a ak sa nikdy nepokúsime spáriť 1 rodiča dva krát, môžme si byť istý, že to ide.

Keďže každá cesta bude mať 1 hranu, súčet dĺžok ciest musí byť $k$ ak sa to dá. Teda veľmi ľahko získame výsledok.

Optimálne riešenie

Zoberme si inšpiráciu z 1. a 2. podúlohy a prejdime graf DFS-kom, pričom budeme propagovať koľko máme aktuálne aktívnych ciest. Strom budeme prechádzať postupne od listov. Pritom sa nám môže stať, že spropagujeme rôzne počty aktívnych ciest:

• 0 ciest - Ak je vrchol špeciálny musí z neho ísť cesta dohora, lebo pod ním nie sú vrcholy, ktoré by mohli byť druhý koniec cesty.
• 1 cesta - V tomto prípade, ak sme na špeciálnom vrchole tak ju musíme ukončiť a ak nie sme tak ju propagujeme ďalej.
• 2 cesty - Ak je tento vrchol špeciálny tak nemôže byť koncom oboch ciest čiže to nejde. Ak nie je tak ich vieme spojiť do jednej.
• 3 a viac ciest - V tomto prípade neexistuje spôsob ako by sa 2 rôzne mravčie cesty nedotýkali a teda to nejde.

Počas tohoto procesu prechádzania stromu si navyše pamätáme celkovú dĺžku ciest a to tak, že keď sa nachádzame na vrchole, ktorý je začiatok, koniec alebo vrchol, ktorý cestu len propaguje ďalej, pridáme 1 k celkovému počtu vrcholov ciest. Tých bude na konci celková dĺžka ciest plus $k$, teda stačí odčítať $k$.

Časová zložitosť je $O(n)$ a pamäťová je tiež $O(n)$, lebo musíme prečítať celý vstup. Toto platí pre všetky 3 podúlohy vo vzorovom riešení.