Exhaustive search. A minimax algorithm with full exhaustive search is a slow solution with no simple implementation. With the following observation, an exhaustive search solution becomes much cleaner and easier to implement. It doesn't make sense to block a passage after cleaning some other passage. Cleaning the passage increases the mouse's movement options, therefore Dumbo would be better off blocking the other passage before cleaning one.

If Dumbo leaves the mouse running, it will eventually get stuck. Before the mouse gets stuck, Dumbo will only block passages. Which ones should be blocked is a matter of the exhaustive search. Once the mouse is stuck, Dumbo will block all the side passages leading away from the path to the trap and then clean that path. The mouse will have no choice but to run directly into the trap.

Mouse starts the game next to the trap. Root the tree so that the root corresponds to the trap. What happens if Dumbo just leaves the mouse running until it gets stuck? The mouse will get stuck in one of the leaves, Dumbo will block all the side edges on the path leading from this leaf to the root and then clean the dirty edges in this path.

We can calculate the exact number of moves Dumbo needs to win the game if the mouse is caught in a certain leaf. Let's call this the weight of the leaf and denote the weight of a leaf ~l~ with ~w_l~. Note that if Dumbo leaves the mouse running around, it will move to the leaf with the largest weight. On the other hand, Dumbo will try to block the mouse from reaching leaves with large weights.

Suppose the mouse is in node ~v~. Because the mouse starts at depth ~1~, we can safely assume it only moves down the tree towards the leaves. Node ~v~ has ~i~ children ~u_1 \dots u_i~. Without loss of generality, we assume that ~u_1~ is the optimal choice for the mouse and ~u_2~ the second best. Dumbo will want to block the passage to node ~u_1~. Does this affect weights of the leaves in subtrees ~u_2 \dots u_i~? Because edge ~(v, u_1)~ is a side edge from a path from any leaf in subtrees ~u_2 \dots u_i~ to the root, it's already part of their weights and the edge ~(v, u_1)~ has to be blocked anyway. So blocking the passage next to the mouse doesn't change the weights of the leaves in the subtrees. Hence, Dumbo will block the best possible child of the node and mouse will traverse the second best.

From here on, we can generalize the definition of weights for any node. Weight of a node ~v~ is the number of moves Dumbo needs to win if it's his turn and the mouse is currently in node ~v~. Dumbo will block the edge to the heaviest child and the mouse will traverse the edge to the second heaviest one. Hence, weight of a node ~v~ is the weight of second heaviest child or ~1~ if ~v~ only has one child. Weights of nodes can easily be calculated with one tree traversal which takes linear time. The number of moves in the game is equal to the weight of the mouse's starting node.

General case. How does the game change in the general case? The mouse doesn't start the game at depth ~1~, which means it might make a few moves up the tree before going down. Dumbo cannot block upgoing edge, because he would block mouse from reaching the trap. As soon as the mouse makes a move down the tree, the game continues as described in the previous section.

When selecting the next edge to block, Dumbo must therefore not limit himself to outgoing edges of the mouse's current location. Possible candidates are also the side passage on the path from the mouse to the trap.

In the starting position of the game, a path ~P~ leads from the mouse to the trap. Dumbo may not block edges in ~P~, so weights of nodes in ~P~ are undefined. There are multiple subtrees attached to ~P~. Each of these subtrees (actually their roots) has its weight as defined in the previous section.

Suppose the mouse arrives into a subtree ~S_i~. Any blockade Dumbo made on side edges of ~P~ below the depth of ~S_i~ does not count towards its weight ~w_i~. Let's say there were ~B_i~ such moves, therefore Dumbo has to make ~B_i+w_i~ moves in total. What is the minimal ~B_i+w_i~ if Dumbo plays optimally?

We can find this by a binary search over the total number of Dumbo's moves. Whether Dumbo can win in at most ~X~ moves can be verified by simulating a mouse's run up the path ~P~ and testing if all the side edges ~i~ with ~w_i+B_i > X~ have been blocked.

We can present each subtree ~S_i~ with pair ~(d(v, S_i), w_i)~, where ~d(v, S_i)~ is distance of subtree ~S_i~ from node ~v~. Dumbo can only block path to this subtree in the first ~d(v, S_i)~ rounds, then the mouse reaches it. We sort pairs by first component. Let ~L~ be this sorted list of pairs. We will use variable ~B~ to count the number of blocked side paths. Initially, ~B := 0~.

For each pair ~L_i~ in ~L~: If ~L_i(2)+B > X~, the passage has to be blocked and ~B := B+1~. If at any point ~L_i(2)+B > X~ and ~B > L_i(1)~, mouse reached a subtree before Dumbo could block the passage to it, which means Dumbo can't win in ~X~ moves. Otherwise, we found a way for Dumbo to win in ~X~ moves.

Each bisection iteration takes linear time (the list ~L~ doesn't change, it can be reused multiple times). Hence, total running time is ~\mathcal O(n \log n)~.