Green Hackenbush (트리)

문제 설명

1번 정점을 루트로 하는 트리에서 두 명의 플레이어가 Green Hackenbush 게임을 한다. 두 플레이어가 번갈아 가며 트리의 간선 하나를 제거한다. 간선이 제거되면 루트와 연결되지 않는 모든 정점 및 간선도 함께 제거된다. 더 이상 제거할 간선이 없는 플레이어가 패배한다.

루트 정점을 루트로 하는 각 서브트리의 그런디 수는 자식 노드들의 그런디 수에 1을 더한 값들의 비트 XOR과 같다. 스프래그-그런디 정리에 따라 전체 트리의 그런디 수가 0이 아니면 선공이, 0이면 후공이 필승 전략을 가진다.

주어진 트리에서 선공 플레이어의 승패를 판별하라.