jak?

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.

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

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

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

To ja jeszcze dodam, że zgodnie z treścią zadania powinno być n <= 10^5.

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

Skoro już koniec rundy to chciałby ktoś uchylić się wyjaśnić to zadanie? Przesiedziałem nad nim chyba z 15 godzin i na nic nie wpadłem :(

Nie potwierdzam, nie zaprzeczam.

Michale potwierdzam że twoje outy są równe rozmiarowi twojej paczki :D

potwierdzam

potwierdzam

Dzięki za fajną paczkę

potwierdzam

potwierdzam