gra (graf nieskierowany)

[sportowiec1993]

mamy plansze o n polach (piszemy to w 1 wierszu), w kolejnych n-1 wierszach piszemy jak te pola są ze sobą połączone:
w i+1 wierszu znajduje się liczba\(\displaystyle{ a_{1}}\) mówiąca, że pole o numerze i+1 łączy się z polem
\(\displaystyle{ a_{1}}\) np. dane wejściowe:
3
1
1 oznaczają, że na planszy są 3 pola, 1 pole łączy się z 2 oraz 1 pole łączy się z 3.

Dwie osoby A i B grają w grę. Gracze wykonują kolejno ruchy, zaczyna A. W pierwszym ruchu A wybiera niezamalowane pole (oczywiście przed rozpoczęciem gry wszystkie są niezamalowane) . W każdym kolejnym ruchu gracz, na którego przypada kolej zamalowuje wierzchołek, który jest połączony z wierzchołkiem zamalowanym przez 2 gracza. Przegrywa ten który nie może wykonać ruchu.
Znajdź wszystkie pola których wybór w pierwszym ruchu przez A zapewnią mu zwycięstwo. Zakładamy, że gracze postępują optymalnie.

Nie bardzo wiem jak się zabrać do tego. Początkowo chciałem rozważać wierzchołki o najwyższych stopniach, potem odwrotnie... ale mi nie wychodziło
Jak możecie to prosiłbym o jakieś wskazówki

[Fingon]

Rozumiem, że graf jest drzewem, czyli mamy n-1 krawędzi i graf jest spójny. Wtedy, wystarczy wykonać dwukolorowanie drzewa, powiedźmy na, czarno i biało. Jeżeli wierzchołki podzieliły się względem kolorów na równe grupy, ze względu na kolor, to gracz zaczynający zawsze przegrywa, jeśli wierzchołki podzieliły się na nierówne grupy, to gracz zaczynając wygrywa zaczynając grę od dowolnego wierzchołka należącego do grupy z większą ilością wierzchołków. Algorytm można zrealizować prostymi modyfikacjami BFSa lub DFSa.