Zadanie
Ako všetci viete, v našich Nízkych Tatrách v hojnom počte žijú sysle. Býva tam aj syseľ Marián. Svoj príbytok si vybudoval tak, že vyhĺbil na lúke priechodný, pohodlný tunel, ktorý na konci rozšíril na priedušnú, útulnú izbu. V nej opäť vyhĺbil niekoľko priechodných, pohodlných tunelov, ktoré na konci rozšíril na priedušné, útulné izby. Takto pokračoval, v každej už vyhĺbenej priedušnej, útulnej izbe vyhĺbil smerom nadol niekoľko (nula alebo viac) priechodných, pohodlných tunelov. Keď skončil, jeho syslie obydlie tvorilo \(n\) útulných, priedušných izieb spojených \(n-1\) priechodnými, pohodlnými tunelmi. Marián bol so svojím výtvorom náramne spokojný.
Jedného večera, zatiaľ čo riešil syslie veci v jednej zo svojich izieb, začalo vonku mrznúť. Mariánovi bolo jasné, že ak by vyliezol do niektorej izby, ktorá je bližšie k povrchu ako tá, v ktorej práve je, tak by určite prechladol. Nič si z toho však nerobil – uložil sa spať v jednej z prístupných izieb (buď ostal v tej, čo bol, alebo sa presunul niekam hlbšie). No nemohol tušiť, že kvôli ukrutnej zime primrzol neďaleký rybník. Žaba Michal sa teda rozhodol, že si nájde priedušnejší, útulnejší príbytok. A tak zamieril priamo do Mariánovej nory. Vďaka priechodnosti a pohodlnosti tunelov bez problémov doskákal až do priedušnej, útulnej izby v ktorej spal Marián. Marián sa v tú noc prebudil na neúprosné chrápanie jeho novonadobudnutého spolubývajúceho.
Čo má teraz robiť? Marián dobre vedel, že ak by Michala vyhnal, tak by v studenej noci určite ochorel. Na to však nemá srdce. Nechal teda žabu spať, prešiel cez priechodný, pohodlný tunel do vedľajšej priedušnej, útulnej izby a horko-ťažko predsa len zaspal. Keď sa ráno zobudil, žaby už nebolo. Marián si však domyslel, že sa táto situácia bude celú zimu opakovať – akonáhle začne večer vonku mrznúť, Marián si bude musieť nájsť takú priedušnú, útulnú izbu, do ktorej sa vie dostať pomocou priechodných, pohodlných tunelov bez toho, aby liezol smerom nahor (tam by totiž prechladol). Hneď na to k nemu doskáče žaba Michal a Mariánovi nedá svojim chrápaním spať. Teraz Marián potrebuje ujsť do inej izby čo najďalej od žaby bez toho aby vyliezol nad izbu v ktorej bol večer (tam sa mu bude najľahšie zaspávať). Marián si ďalšiu noc radšej naplánuje.
Úloha
Izbám v svojej nore priradil Marián čísla od \(1\) po \(n\). Číslo izby, ktorú vyhĺbil ako prvú (teda izby najbližšie k povrchu) označme \(l\). Hĺbka izby je počet tunelov, cez ktoré treba prejsť smerom nadol, aby ste sa do nej dostali z lúky. Hĺbka izby \(l\) je teda 1 a hĺbka každej inej izby je o 1 väčšia než hĺbka izby nad ňou.
Vzdialenosť medzi dvoma izbami je počet tunelov, cez ktoré musíme prejsť, aby sme sa dostali z jednej do druhej.
Mariánova nora môže vyzerať napríklad takto:
Izbu, kde sa Marián zdržiava večer, označme \(v\). Počas celej noci sa Marián nemôže ani na chvíľu ocitnúť v izbe s menšou hĺbkou, než hĺbka izby \(v\). To znamená, že ani počas presunu z izby \(v\) do izby, kam sa prvotne uloží spať, ani počas nočného úteku od žaby nemôže Marián ani len prechádzať cez izbu s menšou hĺbkou ako má izba \(v\). Samozrejme, aj obe izby, kde bude Marián spať, musia byť aspoň tak hlboko ako \(v\).
Marián potrebuje o každej izbe zistiť, aká je dobrá. To znamená, že pre každú izbu ho zaujíma odpoveď na otázku “Ak by som sa večer zdržiaval v tejto izbe a izbu na spanie by som si zvolil čo najlepšie, ako ďaleko od žaby sa mi v noci podarí dostať?” Inými slovami, pre každú izbu \(x\) ho zaujíma najväčšia možná vzdialenosť medzi dvojicou izieb \(y, z\) takou, že z izby \(x\) sa vie dostať do izby \(y\) a z izby \(y\) do izby \(z\) bez toho, aby musel vyliezť do menšej hĺbky než má izba \(x\).
Pomôžte úbohému sysľovi!
Formát vstupu
V prvom riadku sú dve čísla \(n\), \(l\) (\(1 \leq l \leq n \leq 150\,000\)) – počet izieb v Mariánovej nore a číslo izby, ktorá je priamo prepojená s lúkou (a má teda hĺbku \(1\)). Nasleduje \(n-1\) riadkov s dvojicami čísel izieb \(a_i, b_i\), ktoré sú prepojené tunelom. Je zaručené, že z každej izby sa dá postupnosťou tunelov dostať do každej inej práve jedným spôsobom. Izbičky s chodbami teda tvoria strom.
V prvej sade testovacích vstupov navyše platí, že z každej izby ide najviac jeden priechodný, pohodlný tunel do izby s väčšou hĺbkou. To znamená, že nora sa nerozvetvuje, iba stále klesá dodola.
Formát výstupu
Vypíšte \(n\) riadkov. V \(i\)-tom z nich vypíšte hľadanú vzdialenosť pre izbu \(i\), ako je popísané v časti Úloha
.
Príklad
Input:
4 2
2 3
4 1
3 4
Output:
0
3
2
1
Toto je príklad vstupu z prvej sady.
Input:
7 3
4 7
2 1
6 2
5 2
3 4
5 3
Output:
0
2
5
1
2
0
0
Toto je syslia nora z obrázku v Úlohe. Ak je Marián večer v niektorej z izieb 1, 6 alebo 7, má smolu a musí v nej ostať po celú noc (teda bude od žaby vzdialený nula). Ak je večer v izbe 2, môže sa uložiť spať do izby 6 a počas noci utiecť do izby 1 (vzdialenosť 2). Ak je večer v izbe 3, môže ísť spať napríklad do izby 1 a v noci sa presunúť do izby 7 (vzdialenosť 5). Ak začína v izbe 4, môže ostať spať v nej a v noci utiecť do izby 7 (vzdialenosť 1). Ak bude večer v izbe 5, môže sa uložiť v izbe 6 a v noci prejsť späť do izby 5 (vzdialenosť 2).
Pred čítaním vzorového riešenia tejto úlohy silno odporúčame mať prečítané články z kuchárky o grafoch a prehľadávaní do hĺbky.
Formálne si popíšeme, čo je vlastne našou úlohou. Sysľova nora je zakorenený strom (koreňom je izba číslo \(l\)). Pre každý vrchol v tomto strome nás zaujíma dĺžka najdlhšej cesty v jeho podstrome.
Riešenie prvej sady
Spomenieme stručne riešenie prvej sady – v nej nám bolo sľúbené, že z každej izby vedie (najviac) jeden tunel do hlbšej izby. Keď sa v takejto nore Marián v niektorej izbe rozhoduje, kam si má ľahnúť a následne kam utiecť, má jednoduchú optimálnu stratégiu – ľahne si do najhlbšej izby v nore, po príchode žaby utečie do tej v ktorej začal; vyššie vyjsť nemôže, smerom nadol je najviac vzdialená predsa najhlbšia izba. Tá bude mať v prvej sade vždy hĺbku \(n\) (keďže sa nora nerozvetvuje, ale stále iba klesá nadol). Jediné, čo teda potrebujeme zistiť, je pre každú izbu, ako hlboko vlastne je – označme si hĺbku i-tej izby \(h_i\); odpoveď pre izbu \(i\) bude \(n-h_i\).
Hĺbku každej izby vieme zistiť jednoduchým prehľadávaním do hĺbky – nastavíme hĺbku izby \(l\) na \(1\), začneme z nej prehľadávať a izbe ktorá je s ňou spojená nastavíme hĺbku \(2\). Následne pokračujeme v prehľadávaní z nej, teda izbe ktorá je spojená s ňou (a nie je to izba \(l\)) nastavíme hĺbku \(3\). Teraz pokračujeme v prehľadávaní z nej, a tak ďalej.
Z každej izby budeme prehľadávať práve raz, teda časová zložitosť je \(O(n)\). Noru si môžeme pamätať ako graf so zoznamami susedov pre každý vrchol, pamäťová zložitosť bude teda tiež \(O(n)\) (v prvej sade bolo však vrcholov málo, takže ľubovoľná implementácia bola v poriadku).
#include <iostream>
#include <vector>
using namespace std;
struct vrchol
{
bool videl = false;
int hlbka;
vector<int> hrany;
};
vector<vrchol> graf;
void dfs(int v)
{
graf[v].videl = true;
for(int i=0;i<graf[v].hrany.size();++i)
{
int k = graf[v].hrany[i];
if(graf[k].videl) continue; // ak sme vrchol k videli, je to izba nad nami
graf[k].hlbka = graf[v].hlbka + 1; // inak je pod nami a ma hlbku o 1 vacsiu
dfs(k);
}
}
int main()
{
int n,l;
cin >> n >> l;
--l;
graf.resize(n);
for(int i=0;i<n-1;++i)
{
int a,b;
cin >> a >> b;
--a,--b;
graf[a].hrany.push_back(b);
graf[b].hrany.push_back(a);
}
graf[l].hlbka = 1;
dfs(l);
for(int i=0;i<n;++i)
cout << n-graf[i].hlbka << "\n";
return 0;
}
Čo nám chýbalo pre rozvetvujúcu noru?
Predstavme si, že Marián si pre zvolenú začiatočnú miestnosť už vybral, kam sa najprv uloží spať. Jeho úniková cesta môže byt len troch rôznych typov:
vráti sa do začiatočnej izby a tu ostane
prejde cez začiatočnú izbu a bude pokračovať niekam inam
do začiatočnej izby sa nevráti a ani cez ňu neprejde
Žiadne iné scenáre sa neodohrajú, takže ak každý z nich rozoberieme, určite sme na nič nezabudli a máme celé riešenie. Pre každú izbu samozrejme povieme najväčší výsledok z hore uvedených možností.
V prvom type cesty utečie Marián rozdiel hĺbok izby v ktorej začal a v ktorej si najprv ľahol. Spočítame si teda hĺbky izieb rovnako ako v predošlom riešení (prehľadávame vždy z každej doteraz nevidenej izby) a pre každú izbu si zapamätáme najväčšiu hĺbku izby, ktorá je v jej podstrome – označme si túto hodnotu i-tej izby \(maxh_i\). Jedna možná odpoveď pre izbu \(i\) je teda \(maxh_i - h_i\) (v druhom príkladovom vstupe to bola odpoveď napríklad pre izby 1,4,6,7 – obrázok sa nachádza na konci vzorového riešenia).
Toto riešenie sa však dá triviálne vylepšiť na druhý spomínaný typ cesty, ak je izba priamo spojená s aspoň dvoma hlbšími izbami. V takom prípade, po ľahnutí do najhlbšej možnej izby a vrátení sa do začiatočnej, sa Marián naviac poberie cez inú, priamo spojenú hlbšiu izbu a ľahne si do niektorej izby dosiahnuteľnej z nej. Do ktorej izby sa mu oplatí si ľahnúť? Čím hlbšie pôjde Marián cez inú izbu ako tú, pod ktorou si najprv ľahol, tým bude ďalej od žaby. Určite si teda bude chcieť nakoniec ľahnúť v čo najhlbšej izbe, ako sa len dá. Zapamätáme si dve najväčšie \(max_h\) izieb s ktorými sme priamo spojení v izbe \(i\); nech je to \(maxh_j\) a \(maxh_k\). Najprv teda pôjdeme z izby \(i\) v hĺbke \(h_i\) do izby s hĺbkou \(maxh_j\) cez izbu \(j\). Následne od žaby utečieme tak, že sa vrátime naspäť do izby \(i\) (zatiaľ teda vzdialenosť \(maxh_j - h_i\)) a potom pôjdeme do izby v hĺbke \(maxh_k\) cez izbu \(k\) – tým si prilepšíme o vzdialenosť \(maxh_k - h_i\). Dokopy sme teda prešli od žaby \(maxh_j - h_i + maxh_k - h_i = maxh_j + maxh_k - 2 \times h_i\) (v druhom príkladovom vstupe to bola odpoveď napríklad pre izby 2,3).
Posledný prípad je taký, že si Marián chce najprv ľahnúť niekam hlbšie a potom utiecť do druhej izby bez toho aby sa vrátil do začiatočnej – vlastne chce využiť nejakú existujúcu najdlhšiu cestu ktorá neobsahuje tú izbu, v ktorej práve je. To je jednoducho len maximum z už vypočítaných odpovedí všetkých priamo spojených hlbších izieb. Keby v druhom príkladovom vstupe bol od izby 1 tunel do hlbšej izby 8 a od izby 6 tunel do hlbšej izby 9, odpoveď pre izbu 2 je 4 (druhým spôsobom) – Marián si ľahne napríklad do izby 8 a potom utečie do izby 9. Pre izbu 5 je odpoveď rovnaká – Marián má na výber buď spôsob 1 (utiecť do najhlbšej izby s hĺbkou o 3 väčšou) alebo využiť už nájdenú odpoveď pre izbu 2 – a tá je teda lepšia.
Graf si budeme pamätať rovnako ako v riešení prvej sady - ako zoznamy susedov, s konštantne veľa premennými pre každý vrchol navyše (\(h_i, maxh_i, odpoved_i\)). Pamäťová zložitosť je teda \(O(n)\).
Časová zložitosť bude tiež rovnaká – \(O(n)\) – keďže opäť prehľadávame z každej izby práve raz, a pre každú raz spočítame \(h_i, maxh_i\) a \(odpoved_i\).
#include <iostream>
#include <vector>
using namespace std;
struct vrchol
{
vector<int> tunely;
bool videna = false;
int hlbka,maxcesta;
};
vector<vrchol> nora;
// vypocita odpoved pre vrchol v, a vrati najvacsiu dosiahnutelnu hlbku cez vrchol v
int dfs(int v)
{
nora[v].videna = true;
int maxcesta_synov = 0;
int hlbky[2] = {0,0};
int synovia = 0;
for(int i=0;i<nora[v].tunely.size();++i)
{
int k = nora[v].tunely[i];
if(nora[k].videna) continue;
synovia++;
nora[k].hlbka = nora[v].hlbka + 1;
int hlbkasyna = dfs(k);
maxcesta_synov = max(maxcesta_synov,nora[k].maxcesta);
if(hlbkasyna>hlbky[0]) swap(hlbky[0],hlbkasyna);
if(hlbkasyna>hlbky[1]) swap(hlbky[1],hlbkasyna);
}
if(synovia==0)
{
//som list, nemam v podstrome ziadnu cestu
nora[v].maxcesta = 0;
return nora[v].hlbka;
}
//bud pouzijem maximalnu cestu v podstrome mojich synov
nora[v].maxcesta = maxcesta_synov;
//alebo spravim cestu najhlbsi_syn -> ja ( -> druhy najhlbsi,iny syn ak mam viac synov)
if(synovia==1)
nora[v].maxcesta = max(nora[v].maxcesta, hlbky[0] - nora[v].hlbka);
else
nora[v].maxcesta = max(nora[v].maxcesta, hlbky[0]+hlbky[1] - 2*nora[v].hlbka);
return hlbky[0];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,l,i;
cin >> n >> l;
nora.resize(n);
l--;
for(i=0;i<n-1;++i)
{
int a,b;
cin >> a >> b;
--a,--b;
nora[a].tunely.push_back(b);
nora[b].tunely.push_back(a);
}
nora[l].hlbka = 1;
dfs(l);
for(i=0;i<n;++i)
cout << nora[i].maxcesta << "\n";
return 0;
}
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.