Wróciłem dzisiaj do tego zadania, omówię rozwiązanie, które wchodzi na 100pkt.
Pierwsze spostrzerzenie jest dość oczywiste.
1 - Poprawny szablon musi zaczynać się w jakimś liściu i iść ścieżką do jakiegoś innego wierzchołka. Gdyby tak nie było, to krawędź od liścia do rodzica liścia nie byłaby użyta. Co więcej możemy zacząć z dowolnego liścia i puścić algorytm dfs do znalezienia wszystkich kandydatów na wynik. Trzeba tutaj uważać, żeby nie trzymać w dfs-ie całego napisu, dlatego robimy drzewo trie. Ukorzeniamy je w liściu i napełniamy to drzewo trie idąc dfs-em od liścia. Zauważmy, że będziemy mieć maksymalnie około n kandydatów na wynik.
No to mamy n kandydatów i trzeba umieć jakoś sprawdzić, który jest poprawnym szablonem. Zrobimy to w dwóch fazach. Chcemy dla każdego wierzchołka w drzewie trie naliczyć vector par (a,b), które mówią nam, że ciąg na ścieżce od wierzchołka a do wierzchołka b w oryginalnym drzewie z treści zadania ma taką samą wartość jak nasz wierzchołek w drzewie trie na ścieżce od korzenia drzewa trie do niego. Żeby to naliczyć, skorzystamy z tego, że n <= 2000, czyli możemy z każdego wierzchołka w drzewie z treści zadania puścić dfs-a, bo będziemy mieć wtedy o(n^2). Tak wiec robimy puszczamy dfs-a z każdego wierzchołka. Powiedzmy, że puściliśmy go aktualnie od wierzchołka x. W dfs-ie trzymamy aktualny wierzchołek w oryginalnym drzewie, oraz jaki numer ma ścieżka od x do y, (gdzie y, to aktualny wierzchołek w dfs-ie). Idziemy tylko wtedy, gdy dana literka ma krawędź w drzewie trie. Tak więc pozbyliśmy się za pomocą drzewa trie niepotrzebnego kopiowania napisów, wszystko mamy szybciutko.
Mamy policzone dla każdego wierzchołka w drzewie trie jakie ścieżki w oryginalnym drzewie mają taką samą wartość jak ścieżka z korzenia drzewa trie do niego, teraz musimy jakoś sprawdzić, czy da się całkowicie pokryć drzewo tymi ścieżkami. Zrobimy to korzystając z programowanie dynamicznego na drzewie. Dodajemy w wierzchołkach a i b, odejmujemy 2 w wierzchołku lca(a,b), gdzie lca(a,b) to najniższy wspólny przodek wierzchołków a i b. Przetwarzając it-y wierzchołek dp[v] = suma dp dzieci + to co dodaliśmy / usuneliśmy. Zauważmy, że krawędź do rodzica jest pokryta wtedy i tylko wtedy, gdy dp[v] > 0. Jeżeli dla wszystkich wierzchołków nie licząc korzenia dp[v] > 0, to drzewo da się pokryć takim szablonem, w przeciwnym razie nie.
Pozostaje pytania jaką ten algorytm ma złożonność. Kandydatów na wynik mamy około n, każdego przetwarzamy w o(n), czyli przetworzenie kandydatów ma o(n^2). Taką samą złożonność ma znalezienie kandydatów. Pozostaje pytanie co z lca par wierzchołków a i b oraz jak odtworzyć wynik. Limity zadania pozwalają nam na o(n^2* log n), czyli lca można znajdywać klasycznie jump pointerami w o(log n) oraz skoro mamy n kandydatów i każdy ma długość co najwyżej n-1, to możemy wrzucić wszystkie wyniki (w stringach) na seta / na vector i posortować i wypisać w kolejności posortowanej. Takie rozwiązanie ma o(n^2 * lg n) i jak najbardziej wchodzi na 100pkt, za bardzo dużym zapasem. Da sie to usprawnić do o(n^2) korzystając z tego, że nie trzeba liczyć lca za każdym razem oddzielnie w logu, tylko skoro mamy n <= 2000, to możemy dfs-em spreprocesować sobie lca dla każdej pary albo oddzielnie, albo wtedy gdy naliczamy te wszystkie pary (a,b). A jeśli chodzi o wypisywanie wyniku to drzewo trie daje nam porządek alfabetyczny wiec wydaje się, że można poprostu dfs-em w o(n^2) znaleźć wszystkie wyniki, tylko jest jeden problem, że jak pasuje szablon x, to szablon równy x, tylko w odwróconej kolejności też jest szablonem, wiec możemy zbudować już pod koniec drugie drzewo trie, na które dodamy wszystki oryginalne szablony spełniające wynik i wszystkie odwrócone szablony. W ten sposób możemy puścić dfs-a na takim drzewie trie i dostaniemy o(n^2).
Więcej o drzewach trie można zobaczyć np. tutaj:
-
https://www.youtube.com/watch?v=MBIe1gBiWwY
-
https://www.youtube.com/watch?v=RDRJpl-jUG4
- Było też takie zadanie na oi Midas.
Więcej o lca i jump pointerach:
- zadanie randka oi
- zadanie komiwojażer bajtazar oi
- zadanie odwiedziny oi
-
https://www.youtube.com/watch?v=4tzs0brpbWA
-
https://www.youtube.com/watch?v=IRMdwFMJ_NI&t=2041s
-
https://www.youtube.com/watch?v=ub1E2lSuafc
-
https://www.youtube.com/watch?v=x3pf0aiWgnI
Jeżeli kogoś interesuje ta sztuczka z dodawaniem 1 w liściach i odejmowaniem 2 w lca, to było takie zadania z ceoia, bardzo polecam:
https://oj.uz/problem/view/CEOI17_oneway
Mam nadzieję, że rozwiązanie jest dobrze opisane.