Once the piece enters some subtree, it never exits from it until there is no more coin in it. Also, once the piece exits from a subtree, it never reenters it. Thus, we can solve the problem for each subtree recursively.

Let \(f(v)\) be the number of coins the first player gets minus the number of coins the second player gets when they play the game in the subtree rooted at \(v\). We compute \(f(v)\) recursively along the tree.

The optimal play

When they play the game in the subtree rooted at \(v\), the first player gets the coin on \(v\) first. Then, the second player chooses the vertex to which the piece goes. To consider the optimal choice, we will divide the children \(u\) of \(v\) into three categories:

1. \(f(u)\lt 0\) and the size of the subtree rooted at \(u\) is even;
2. \(f(u)\ge 0\) and the size of the subtree rooted at \(u\) is even;
3. the size of the subtree rooted at \(u\) is odd.

If a player moves the piece to a vertex of category 1, he will be able to get more coins than the opponent does (in that subtree), and he will get to choose a child of \(v\) again. That is, moving the piece there does not make him lose anything, so if a vertex of category 1 is available among the children of \(v\), he should always choose it.

If a player moves the piece to a vertex of category 2, he will never be able to get more coins than the opponent does, then he will get to choose a child of \(v\) again. That is, whether he chooses that vertex or not does not affect the turns, and there is no profit in choosing it, so he has no reason to choose it; he should avoid choosing a vertex of category 2 unless he is forced to do so.

If a player moves the piece to a vertex of category 3, after all the coins are taken from the subtree rooted there, he will return the piece to \(v\) himself. That is, the opponent will choose a child of \(v\) next, so he should immediately choose the “best” subtree, or the opponent will do so. Thus, if a vertex of category 3 is available among the children of \(v\), he should choose the one with the minimum \(f(u)\). As a result, if there are multiple vertices of category 3, the second player will take one with the minimum \(f(u)\), the first player will take one with the second minimum \(f(u)\), the second player will take one with the third minimum \(f(u)\), and so on.

We can solve the problem by computing \(f(v)\) based on this optimal play. We need to sort the vertices of category 3, so the solution will have the complexity of \(O(n \log n)\).

Sample Implementation in C++

Sample Implementation in Python