About bipartite graph

A graph without an odd cycle is called a bipartite graph. This is equivalent to:

• one can paint vertices in two colors so that no edge connects vertices of the same color.

For such a graph, one can partition the vertex set into two sets by the color. These set are called partite sets (or simply parts).
The partite sets of a connected bipartite graph are unique, and they can be found by performing DFS (Depth-First Search) or BFS (Breadth-First search) from an arbitrary vertex.

Solution to the problem

A tree is a bipartite graph. If the partite sets have sizes \(A\) and \(B\), then one can add at most \(AB-(N-1)\) edges. The order of adding edges does not affect to whether one can add an edge. Thus, this game is equivalent to alternately choosing one option from \(AB-(N-1)\) choices, and the one who are unable to choose loses. If \(AB-(N-1)\) is odd, the player who makes the move first wins; if it is even, the second wins.
The problem can be solved by deciding firsthand which partite set each vertex belongs to, enumerating all the choices of edges, and storing it into a set.