CF2013F2 Game in Tree (Hard Version)

This is the hard version of the problem. In this version, it is not guaranteed that $ u = v $ . You can make hacks only if both versions of the problem are solved. Alice and Bob are playing a fun game on a tree. This game is played on a tree with $ n $ vertices, numbered from $ 1 $ to $ n $ . Recall that a tree with $ n $ vertices is an undirected connected graph with $ n - 1 $ edges. Alice and Bob take turns, with Alice going first. Each player starts at some vertex. On their turn, a player must move from the current vertex to a neighboring vertex that has not yet been visited by anyone. The first player who cannot make a move loses. You are given two vertices $ u $ and $ v $ . Represent the simple path from vertex $ u $ to $ v $ as an array $ p_1, p_2, p_3, \ldots, p_m $ , where $ p_1 = u $ , $ p_m = v $ , and there is an edge between $ p_i $ and $ p_{i + 1} $ for all $ i $ ( $ 1 \le i < m $ ). You need to determine the winner of the game if Alice starts at vertex $ 1 $ and Bob starts at vertex $ p_j $ for each $ j $ (where $ 1 \le j \le m $ ).

N/A

N/A

 Tree from the first example.In the first test case, the path will be ( $ 2,3 $ ). If Bob starts at vertex $ 2 $ , Alice will not be able to move anywhere on her first turn and will lose. However, if Bob starts at vertex $ 3 $ , Alice will move to vertex $ 2 $ , and Bob will have no remaining vertices to visit and will lose.