Tom and Jerry

The enormous-looking game tree is bait. Once we describe a position correctly, the whole game collapses to degree parity.

1. What remains after a move

After at least one path has been chosen, define:

• $F$: the graph containing exactly the still-unused edges. It is a forest because the original graph is a tree.
• $P$: the path chosen on the previous turn.
• $S=V(P)$: all vertices lying on that path.

A legal next path must lie entirely in $F$ and have at least one endpoint in $S$. Older paths matter only because their edges have disappeared.

Call the position even if

$$\deg_F(v)\equiv 0\pmod 2$$

for every $v\in S$.

2. The core game lemma

Lemma. The player to move loses exactly in the even positions.

Every move from an even position goes to a non-even position

Take any legal path $Q$. One of its endpoints, say $s$, belongs to $S$. Because $s$ is an endpoint of $Q$, deleting $Q$ removes exactly one unused edge incident to $s$.

Its degree therefore changes from even to odd. Also, $s$ lies on $Q$, which becomes the active path for the opponent. Hence the opponent's position is not even.

Every non-even position has a move to an even position

Suppose some $s\in S$ has odd degree in $F$. In any connected component, the number of odd-degree vertices is even, so the component of $s$ contains another odd-degree vertex.

Choose the closest such vertex $t$. On the unique path from $s$ to $t$, every strict internal vertex has even degree in $F$: an odd internal vertex would be closer to $s$ than $t$ was.

Choose this $s$-$t$ path as the move. It is legal because $s\in S$. After removing it:

• each endpoint had odd degree and loses one edge, becoming even;
• each internal vertex had even degree and loses two edges, remaining even.

Thus every vertex of the newly chosen path has even remaining degree. The opponent receives an even position.

Every move removes at least one edge, so the game is finite. The two transition properties above prove the lemma: even positions are losing, and non-even positions are winning. No giant minimax DP required; parity already did the dirty work.

3. Which first paths win?

Let Tom's first path be $P$, and let $d(v)$ be the degree of $v$ in the original tree. Jerry then plays on the forest obtained after deleting the edges of $P$.

For a vertex on $P$:

• an endpoint has remaining degree $d(v)-1$;
• a strict internal vertex has remaining degree $d(v)-2$.

By the lemma, Tom wins precisely when Jerry receives an even position. Therefore:

A first path is winning if and only if both endpoints have odd original degree and every strict internal vertex has even original degree.

This also handles a one-edge path: it has two endpoints and no internal vertices, so it wins exactly when both endpoint degrees are odd.

4. Counting all winning paths

Consider the induced forest consisting only of vertices whose original degree is even. Let its connected components be $C$.

For one component $C$, let $b_C$ be the number of edges with one endpoint in $C$ and the other endpoint an odd-degree vertex.

Choose any two such boundary edges. Their odd endpoints, together with the unique route through $C$, form a path whose endpoints are odd and whose internal vertices are all even. Hence it is winning.

Conversely, every winning path of length at least two has at least one internal vertex. All its internal vertices are even and connected, so they lie in exactly one component $C$. The first and last edges of the path are then exactly two boundary edges of that component. This gives a bijection, so component $C$ contributes

$$\frac{b_C(b_C-1)}2.$$

Because the input is a tree, the same odd vertex cannot have two edges into one even component: those two edges plus the route inside the component would create a cycle. Thus each selected pair really has two distinct endpoints.

Winning paths of length one contain no even internal component, so count them separately. They are precisely the edges joining two odd-degree vertices.

The final formula is

$$\text{answer} = \#\{uv\in E(T): d(u)\text{ and }d(v)\text{ are odd}\} + \sum_C \frac{b_C(b_C-1)}2.$$

5. Algorithm

Build the adjacency list and all degrees. Traverse every connected component induced by even-degree vertices using an iterative DFS. While visiting a component, count every adjacent odd-degree vertex as one boundary edge, then add $b_C(b_C-1)/2$.

Finally, scan every tree edge once and add one whenever both endpoints have odd degree.

The answer can be quadratic in $n$, so it must use long long.

Correctness summary

The parity lemma proves that Tom wins after choosing exactly those paths with odd endpoints and even strict internal vertices. Every such path of length at least two corresponds uniquely to a pair of boundary edges of one even-vertex component, while every winning one-edge path is an odd-odd edge. The algorithm counts both disjoint cases exactly once, so its output is the required number of winning first moves.

Complexity

Each vertex and edge is processed only a constant number of times.

• Time: $O(n)$ per test case
• Memory: $O(n)$