Darth Vader and 3PO on a Tree!

Limits: 1s, 256 MB

Did you watch Star Wars yet? No? You should in your free time.

Now back to Darth Vader and 3PO. Darth Vader and 3PO are playing a game. As you know, 3PO is the most decent robot in the world and always frightened by lightsaber. So they are playing a game on a tree! They initially choose a tree with N nodes. Then they play in turn. In each turn a player can choose a node from the given tree. In each node there are some coins. The amount of coins is equal to the distance from this node to the nearest leaf node. Same node cannot be chosen twice by any player. When any player cannot make any further move the game ends. The player who have less coins than other at the end of the game will win the game. Note that in a given tree, it’s possible that 3PO and Darth Vader has the same amount of coins.


This is a companion discussion topic for the original entry at https://toph.co/p/darth-vader-and-3po-on-a-tree