Zadanie

Obec Kmeťovo, ktorá leží v blízkosti Nových Zámkov je veľmi veselé miesto na žitie. Keď sa prechádzate jeho ulicami, neraz sa vám stane, že odvšadiaľ počuť výbuchy smiechu a radosti, proste samé “Hihihi”, “Hahaha”.

Dôvodom takéhoto šťastného nažívania je skvelý pán starosta, ktorý organizuje spoločenský a kultúrny život v dedinke. Každoročne usporadúva Tradičné jarné, letné, jesenné aj zimné slávnosti, na ktorých sa všetci veselia, pijú a hodujú1. A samozrejme, na blížiace sa tradičné zimné slávnosti sa pozýva veľké množstvo tradičných karnevalových sprievodov.

Kvôli tradičnému socialistickému návrhu stavania obcí, je topológiou obce strom. Inak povedané obec Kmeťovo tvoria križovatky pospájané ulicami pričom platí, že medzi každou dvojicou križovatiek existuje práve jedna cesta skladajúca sa za viacerých ulíc.

Naviac, do obce a von z nej sa dá dostať iba cez križovatky, ktoré v strome predstavujú listy, teda sú pripojené iba k jednej križovatke vo vnútri obce.

Pán starosta by chcel do Kmeťova pozvať čo najviac sprievodov, ktoré vojdú do dediny cez nejakú križovatku a potom inou križovatkou vyjdú von, pričom nemôžu prejsť cez žiadnu ulicu dvakrát, čím je ich cesta dedinou jednoznačne určená. Avšak, ako ho upozornil jeden z členov rady obce, nie je rozumné, aby cez nejakú ulicu prešlo priveľa sprievodov, lebo také dupotanie slonov môže vážne narušiť statiku budov. Pre každú ulicu preto určili maximálny počet sprievodov, ktoré ňou môžu prejsť. Teraz sedia nad plánmi dediny a márne premýšľajú, koľko najviac karnevalov vedia pozvať do Kmeťova.

Úloha

Na vstupe dostanete niekoľko stromov s ohodnotenými hranami. Pre každý z nich nás bude zaujímať jedno číslo: najväčší počet ciest od jedného listu k druhému, ktoré vieme vybrať tak, aby po každej hrane išlo nanajvýš toľko ciest, aká je jej hodnota. Dvojicu listov môžeme vybrať viackrát.

Formát vstupu

Na prvom riadku vstupu je číslo \(z\) – počet vstupných sád. Nasleduje \(z\) vstupných sád. Každá začína číslom \(n\) (\(2 \leq n \leq 10^5\)) – počtom vrcholov. Za ním nasleduje \(n-1\) riadkov, každý s trojicou čísel \(x\), \(y\), \(c\) (\(1 \leq x,y \leq n\), \(1 \leq c \leq 10^6\)) s nasledovným významom: medzi vrcholmi \(x\) a \(y\) vedie hrana s hodnotou \(c\).

Môžete predpokladať, že každý graf na vstupe je naozaj súvislý strom.

Formát výstupu

Pre každú vstupnú sadu vypíšte jeden riadok obsahujúci jedno číslo – najväčší počet ciest, ktoré vieme vybrať spĺňajúc podmienky zadania.

Príklad

Input:

3
4
1 2 2
1 3 2
1 4 2
2
1 2 2
3
1 2 2
2 3 1

Output:

3
2
1

V prvej sade sú listovými vrcholy \(2\), \(3\), \(4\) a jediná možnosť, ako spomedzi nich vybrať 3 dvojice je vybrať každú dvojicu raz.

V druhej sade máme len dva vrcholy, každý má len jedného suseda, čiže oba sú listové. Vyberieme ich dvakrát.

V tretej sade sú listovými vrcholy \(1\) a \(3\), vybrať ich vieme len raz.

  1. Naviac je to príjemné spestrenie od tradičných pondelkových diskoték a tradičných umeleckých štvrtkov.↩

Na začiatok si rozoberieme jeden triviálny prípad. Ak \(n = 2\), odpoveď je snáď zjavná. Všetky ostatné prípady budeme riešiť stromovou rekurziou.

Náš stromček si zavesíme za ľubovoľný nelistový vrchol (vrchol stupňa aspoň 2). V každom vrchole nás budú zaujímať tri hodnoty: Najväčší možný počet ciest, ktoré môžu končiť v danom podstrome a prechádzať cez náš vrchol, koľko z nich nevieme uzavrieť priamo v tomto podstrome (a teda musia prechádzať cez náš vrchol) a nakoniec koľko ciest vieme najviac uzavrieť v našom podstrome, pokiaľ už poznáme predošlé dve hodnoty.

Tieto tri hodnoty z listových vrcholov by mali byť celkom zjavné, preto sa zameriame už len na vnútorné vrcholy stromu. V každom máme niekoľko synov s ich hodnotami. Najprv zistíme druhú hodnotu. Pozrieme sa na syna s najväčšou druhou hodnotou a odrátame od nej prvé hodnoty všetkých ostatných1. Prvú hodnotu získame tak, že nasčítame prvé hodnoty všetkých synov.

Pozor, hodnota hrany do otca nám môže prvú aj druhú hodnotu trošku zrezať. Porozmýšľajte, čo robiť, pokiaľ by nám po tomto orezaní ostal počet uzatvoriteľných ciest v podstrome (\(prva\_hodnota - druha\_hodnota\)) nepárny. Nad poslednou hodnotou sa budete musieť trošku zamyslieť. (Nedáme vám predsa celý návod, ako to vypočítať, nie?) Opäť to bude súvisieť s hodnotami synov a s tým, ako presne nám hodnoty oreže hrana do otca.

Taktiež na zamyslenie ostane doriešiť, ako z týchto troch hodnôt v koreni vypočítať celú odpoveď.

  1. Ak dostaneme kladné číslo, je celkom zjavné, že aspoň toľko nám ich musí ostať neuzatvoriteľných, ak záporné, vieme uzavrieť všetky. Jedným možným spôsobom by bolo vždy uzatvoriť cestu medzi dvojicou synov, ktorí majú najvyššiu druhú hodnotu, skúste si dokázať prečo je to tak. Samozrejme, v riešení nás zaujímajú iba hodnoty a teda netreba riešiť, kto s kým a ako sa pospája.↩

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ť.