Dajcie plusa jak wasze rozwiązanie się bezpośrednio uogólnia na więcej niż 3 ścieżki i minusa jak nie (i macie 10 punktów).

A to mogło jury prosić o 4 ścieżki w takim razie :P

na szczęście już spaliłeś ten pomysł na przyszłość, więc możemy spać spokojnie :P

da się w ogole zrobic 4 sciezki z taka sama zlozonscia?

No tak, ja szukam k ścieżek w O(n*log(n)*f(k)). Tzn no kod by miał znacznie gorszą stałą, więc go optymalizowałem praktycznie rozważając przypadki na palcach, ale się uogólnia na większe k.

Trik jest taki, że jak ukorzenisz sobie to drzewo, to no będzie jakaś ścieżka, która nie jest "nad żadną inną", czyli no dla jakiejś ścieżki możesz ją gdzieś położyć i wyciąć jakiś przedział preorder (nieco się różni ten przedział zależnie czy ta ścieżka by miała być pionowa czy nie, ale w obu przypadkach to przedział). No to można się przeiterować po tym która to. No to jak wiemy która to, to opłaca się ją tak dopchnąć najniżej jak się da, no bo jak możemy usunąć mniej wierzchołków, to się opłaca. No więc wszyscy kandydaci na miejsca gdzie damy tę ścieżkę są rozłączni (tzn. to rozłączne przedziały). No to jeśli tych kandydatów jest co najmniej 2k-1, to na pewno się będzie dało tę ścieżkę gdzieś położyć (bo każda z pozostałych k-1 na każdej głębokości ma co najwyżej dwa wierzchołki), więc możemy ją w ogóle usunąć z listy ścieżek, a jak jest <=2k-2 kandydatów, to się zbranchować. No trzeba jeszcze znajdować takich podstawowych "statycznych" kandydatów oraz kandydatów nad innymi ścieżkami (no bo może jakąś starą ścieżkę chcemy przykryć nową), ale to już chyba mniej ciekawe.

jak?

>mogliśmy prosić o 4 ścieżki
A widziałeś kiedyś bałwana złożonego z 4 kul xddd?

Nie widziałem bałwana złożonego z 4 kul, ale w prostszej wersji zadanie mogło być o budowaniu armat, bo te zazwyczaj mają dwie kule