Dla każdej krawędzi z daną wysokością podatku szukam ścieżek, dla których ta krawędź jest pierwszą krawędzią o tym podatku.

Więc po jednej stronie tej krawędzi patrzę na wszystkie wierzchołki do których można dojść bez przechodzenia przez inne krawędzie o tym samym podatku, i dodaję je do tablicy haszującej gdzie kluczem jest suma wyższych podatków (reprezentowanych przez losowe liczby), a wartością jest liczba wierzchołków.

Po drugiej stronie danej krawędzi przechodzę przez całe drzewo po tej stronie i dla każdego wierzchołka po tej stronie liczę ile brakuje wyższych podatków, i patrzę w tablicy haszującej ile jest pasujących wierzchołków po drugiej stronie.

Też tak robię. Jak zliczasz ścieżki o danej sumie w O(n)? Ja mam to w O(n log n) (i dostałem 4/10).

Moje rozwiązanie jest w O(n^2) (średnio), ale tylko 6/10, trochę za wolne.

Zaczynam od najwyższych podatków. Jak już ustalę ile jakich chcę zapłacić wysokich podatków dla każdego poziomu, to te wysokie podatki reprezentuję przez losowe liczby modulo liczba pierwsza, i szukam takich ścieżek żeby suma się zgadzała modulo p.

Potwierdzam

Zawsze można zrobić Reverse engineering kodów Marcina lub Marka: https://sio2.mimuw.edu.pl/c/pa-2018-1/solutions/?category=2739

Potwierdzam paczki (poza large2 i large3) i hasza.

Potwierdzam obie paczki.

potwierdzam hasz

Potwiedzam paczki i hash

Potwierdzam

Potwierdzam

Potwierdzam hash

Potwierdzam wszystkie testy.

Potwierdzam, ale trochę mi działało :/

Potwierdzam wszystko.

Dorzucam 10000 testów, w połowie N, M <= 7, w drugiej N, M <= 100.
https://drive.google.com/open?id=1ORIMk13FvumSkaBq48eLEYwT6suyDZ3F
Na górze zmieniamy ścieżkę do rozwiązania. Mój hasz: 383706995