CF2271H2 Personal Issues (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $ t \le 10^4 $ , $ n \le 2 \cdot 10^5 $ and the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ . You can hack only if you solved all versions of this problem. The rivals Axial and Nife have had yet another argument, and they decided to settle it by playing a game on a tree. They are given a tree with $ n $ vertices numbered from $ 1 $ to $ n $ . Each vertex contains either $ 0 $ or $ 1 $ . Initially, two distinct vertices $ x $ and $ y $ contain $ 0 $ , and all other vertices contain $ 1 $ . The players take turns, with Axial going first. On each turn, the current player chooses a vertex $ v $ containing $ 1 $ and changes its value to $ 0 $ . Before changing the value of $ v $ , let $ c_v $ be the number of neighbors of $ v $ that contain $ 0 $ . If $ c_v = 1 $ , the current player gets one point. Otherwise, they get no points. The game ends when all vertices contain $ 0 $ . Let $ p $ and $ q $ be the final scores of Axial and Nife, respectively. Axial wants to maximize $ p - q $ , while Nife wants to minimize it. Assuming both players play optimally, determine the value of $ p - q $ at the end of the game.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ x $ , and $ y $ ( $ 2 \le n \le 2 \cdot 10^5 $ , $ 1 \le x, y \le n $ , $ x \ne y $ ) — the number of vertices in the tree and the two vertices that initially contain $ 0 $ . Each of the next $ n - 1 $ lines contains two integers $ u $ and $ v $ ( $ 1 \le u, v \le n $ , $ u \ne v $ ), denoting an edge between vertices $ u $ and $ v $ . It is guaranteed that the given graph is a tree. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single integer — the value of $ p - q $ at the end of the game.

In the figures below, blue vertices initially contain $ 0 $ , while white vertices initially contain $ 1 $ . For the first example, the initial state is: Axial changes vertex $ 3 $ to $ 0 $ . It has exactly one neighbor containing $ 0 $ , so Axial gets one point. Therefore, $ p - q=1 $ . For the second example, the initial state is: Axial can change either vertex $ 2 $ or vertex $ 3 $ to $ 0 $ and get one point. After that, the remaining vertex has two neighbors containing $ 0 $ , so Nife gets no points. Therefore, $ p - q=1 $ . For the third example, the initial state is: The only possible move is to change vertex $ 2 $ to $ 0 $ . It has two neighbors containing $ 0 $ , so Axial gets no points. Therefore, $ p - q=0 $ .