Gra jest dwuosobowa przeprowadzona na wyżej zdefiniowanym drzewie $T$, gdzie wierzchołek jest zadany jako para $(i, v)$ oznaczająca, że wierzchołek znajduje się w $i$-tym drzewie $(0 \le i \le D)$ w wierzchołku $G$ o numerze $v$ $(1 \le v \le n)$. W jednym ruchu gracz może przesunąć pionek wzdłuż krawędzi, ale nie może wrócić do takiej pary $(i, v)$, która była już odwiedzona. Gracze grają na przemian i przegrywa ten gracz, który nie może już wykonać ruchu. Należy założyć, że gracze grają optymalnie.
Liczbę takich pasujących par wierzchołków (nazwanymi dodatkowymi krawędziami) $$(A_0, B_0), (A_1, B_1), \dots, (A_{D-1}, B_{D-1})$$ należy wypisać modulo $10^9 + 7$.
Jeżeli $n=2$, to gracz zaczynający grę zawsze może wygrać. Przykładową jego strategią może być zawsze używanie krawędzi z $G$. Wtedy drugi gracz zawsze musi przejść przez dodatkową krawędź, chyba że taka już nie istnieje (i wtedy drugi gracz przegrywa). Istnieje więc $4^D$ sposobów na dodanie dodatkowych krawędzi. Liczbę $4^D \bmod (10^9 + 7)$ można policzyć szybkim potęgowaniem w czasie $O(\log D)$.
Mając dane dowolne drzewo zakorzenione w pewnym wierzchołku, w czasie liniowym można policzyć dla każdego wierzchołka (na przykład DFS-em) informację, czy wygra gracz zaczynający z pionkiem w tym wierzchołku przy dodatkowym założeniu, że pionek nie może przejść do ojca tego wierzchołka (czyli można się poruszać tylko w poddrzewie tego wierzchołka), w następujący sposób:
Można dzięki temu algorytmowi w czasie $O(n)$ sprawdzić, czy gracz zaczynający z pionkiem w danym wierzchołku $r$ wygra grę przy założeniu, że gracze grają optymalnie.
Przy ograniczeniach $n \le 100, D = 1$ wystarczy wypróbować każdą możliwą dodatkową krawędź i powyższym algorytmem sprawdzić, czy gracz zaczynający grę ma stan wygrywający.
Zamiast wyliczać całe drzewo powstałe przez $D+1$ kopii drzewa $G$, lepiej jest się skupić na spreprocessowaniu odpowiednich informacji drzewa $G$, które będzie można „łączyć” pomiędzy kolejne kopie drzewa $G$.
Dla danych dodatkowych krawędzi $(A_0, B_0), (A_1, B_1), \dots, (A_{D-1}, B_{D-1})$, jeżeli wiadomo, czy wierzchołek $(1, B_0)$ drzewa $T$ jest wygrywający, czy przegrywający, można policzyć w jaki sposób dodanie dodatkowej krawędzi $(A_0, B_0)$ wpłynie na stany wierzchołków $(0, v)$ dla $v\in G$.
Ogólniej można to sobie wyobrażać jako dodanie do pewnego wierzchołka $v$ zakorzenionego drzewa $G$ w wierzchołku $r$ nowego syna $u$ o pewnym stanie (przegrywającym lub wygrywającym) i wyliczenie nowego stanu korzenia drzewa $G$. Taki proces będzie wykonywany łącznie $D$ razy.
Z definicji stanów w algorytmie gry dla dowolnego drzewa wynika, że stan wierzchołka $v$ zmieni się tylko wtedy, gdy $v$ oraz $u$ są stanami przegrywającymi (i wtedy $v$ stanie się stanem wygrywającym). Wtedy ojciec wierzchołka $v$ (oznaczany jako $parent(v)$) zmieni swój stan tylko wtedy, gdy $parent(v)$ jest stanem wygrywającym. Analogicznie można rozpatrywać kolejne przodki wierzchołka $v$. W takim razie, jeżeli stany wierzchołków $v, parent(v), parent(parent(v)), ..., r$ są na zmianę przegrywające, wygrywające, przegrywające, ..., to podczepienie $u$ do wierzchołka $v$ sprawi, że korzeń zmieni swój stan, o ile $u$ jest stanem przegrywającym (i wtedy $v$ będzie nazywany krytycznym stanem przegrywającym dla korzenia $r$). Niech zbiór wszystkich takich $v$, których łańcuszek stanów do korzenia jest takiej postaci, będzie oznaczony jako $C_r$. Da się ten zbiór wyznaczyć dla konkretnego $r$ w czasie $O(n)$.
Zadanie przy ograniczeniach $n \le 1000, D = 1$ można rozwiązać w następujący sposób.
Niech $W$ -- zbiór wierzchołków $G$, dla których rozpoczęcie gry z pionkiem w tym wierzchołku jest stanem wygrywającym, oraz $L$ -- zbiór wierzchołków $G$, dla których rozpoczęcie gry z pionkiem w tym wierzchołku jest stanem przegrywającym. Te zbiory można wyznaczyć w złożoności $O(n^2)$.
Niech drzewo o numerze $0$ będzie $G_0$ (ukorzenione w wierzchołku $1$), a drzewo o numerze $1$ będzie $G_1$ (można dowolnie wybrać korzeń). Nadal zachodzi $G_0 = G_1 = G$, ale zostały odróżnione dla zwięzłości oznaczeń.
Jeżeli korzeń $G_0$ jest w stanie wygrywającym, to po dodaniu dodatkowej krawędzi zmieni swój stan tylko wtedy, gdy do wierzchołka z $C_1$ zostanie doczepiony jakiś korzeń $G_1$, który jest w stanie przegrywającym. Dlatego wynik (liczba sposobów dodania dodatkowej krawędzi, aby korzeń $T$ był w stanie wygrywającym) wynosi $n|W| + (n - |C_1|)|L|$ (korzenie wygrywające $G_1$ można doczepić gdziekolwiek, a przegrywające tylko do wierzchołków spoza $C_1$).
Jeżeli korzeń $G_0$ jest w stanie przegrywającym, to tylko doczepienie korzenia przegrywającego $G_1$ do wierzchołka $C_1$ sprawi, że korzeń $G_0$ zmieni swój stan na wygrywający, dlatego wynik wynosi $|C_1|\cdot|L|$.
Dla $D=1$ można zastosować podejście z podzadania 4, ale należy przyśpieszyć rozwiązanie, czyli szybciej wyznaczyć zbiory $W$ oraz $L$ (nie trzeba przyśpieszyć wyznaczania $C_1$, ponieważ jest wyznaczany w czasie liniowym).
Można to zrobić techniką nazywaną przekorzenieniem drzewa. Należy zacząć od użycia algorytmu z gry dla dowolnego drzewa i policzyć wynik dla każdego poddrzewa przy założeniu, że korzeniem jest $r=1$, a następnie DFS-em zmieniać korzeń na każdy inny wierzchołek. W momencie, gdy jest zmieniany korzeń z $r_1$ na $r_2$ (gdzie $r_2$ jest sąsiadem $r_1$), to mogą się zmienić tylko dwa stany poddrzew (tylko wierzchołków $r_1$ oraz $r_2$), ponieważ reszta poddrzew nie zmieni swojego zbioru wierzchołków. Wystarczy więc przy przekorzenieniu ponownie obliczyć stany gry dla dwóch wierzchołków (a przy wyjściu z DFS-a cofnąć te zmiany). Otrzymujemy dzięki temu wyznaczanie zbiorów $W$ oraz $L$ w czasie $O(n)$, co rozwiązuje to podzadanie także w czasie $O(n)$.
Przy $n\le1000, D\le10^5$, można policzyć następującą wartość.
Niech $L_D$ oznacza liczbę sposobów wybrania wierzchołka początkowego oraz wybrania dodatkowych krawędzi, aby gracz zaczynający przegrał, przy założeniu, że jest $D+1$ identycznych drzew i można zacząć z dowolnego wierzchołka.
Wiadomo już, że na $|C_v|\cdot L_{D-1}$ sposobów można zmienić stan wybranego wierzchołka początkowego $v$ (ponieważ wystarczy dodać krawędź ze stanu przegrywającego do wierzchołka ze stanem krytycznym). Aby $v$ stał się stanem wygrywającym, należy albo zmienić jego stan, albo nie zmienić, w zależności od tego, jaki jest stan $v$ przed dodaniem dodatkowej krawędzi. Dlatego liczba sposobów $L_{D,v}$, aby wierzchołek początkowy $v$ był przegrywający, wynosi $|C_v|\cdot L_{D-1}$ gdy $v\in W$ oraz $n^{2D}-|C_v|\cdot L_{D-1}$ gdy $v\in L$, przy czym $L_0 = |L|$.
Mamy więc \[ L_D = \sum_v L_{D,v} = \sum_{v\in W} |C_v|\cdot L_{D-1} + \sum_{v\in L} (n^{2D} - |C_v|\cdot L_{D-1}) = |L|n^{2D} + \left(\sum_{v\in W} |C_v| - \sum_{v\in L} |C_v|\right)L_{D - 1}, \] gdzie $|L|n^{2D}$ oraz $\left(\sum_{v\in W} |C_v| - \sum_{v\in L} |C_v|\right)$ można spreprocessować w $O(n + \log D)$.
Szukana liczba w zadaniu wynosi $N^{2D} - L_{D,1}$ (pionek jest początkowo położony w wierzchołku $1$ drzewa $0$).
Mając wyznaczone w $O(n^2)$ liczby $|W|, |L|, \sum_{v\in W} |C_v|$ można wyznaczyć $L_D$ w czasie $O(D)$ podanym wzorem. Otrzymujemy więc rozwiązanie o złożoności czasowej $O(n^2 + D)$.
Gdy $D\le10^5$ oraz nie ma dodatkowego ograniczenia na $n$, można zastosować powyższe rozwiązanie, ale przyśpieszając wyznaczanie liczności zbiorów $C_v$ za pomocą przekorzenienia, tak jak w podzadaniu 5.
Gdy nie ma dodatkowych ograniczeń, w porównaniu do poprzedniego zadania, należy szybciej wyznaczyć liczbę $L_{D,1}$.
Znając wartość $L_a$ oraz $L_b$, można wyznaczyć wzór na wartość $L_{a+b}$. Dzięki temu można skorzystać z techniki analogicznej do szybkiego potęgowania do obliczenia $L_D$, czyli na przykład poprzez wyznaczenie liczb $L_1, L_2, L_4, L_8, \dots$ i domnażając te potęgi, których bity są zapalone w $D$.
Alternatywnie, swoim ulubionym sposobem można wyprowadzić wzór na postać jawną rekurencji liniowej $L_D$, otrzymując wzór $L_{D-1} = |L|\frac{n^{2D}-E^D}{n^2-E}$ dla $E=\left(\sum_{v\in W} |C_v| - \sum_{v\in L} |C_v|\right)$, co można wyliczyć szybkim potęgowaniem oraz odwrotnością modulo.