CF2271H2 Personal Issues (Hard Version)

这是该问题的困难版本。两种版本之间的区别在于本题中 $t \le 10^4$，$n \le 2 \cdot 10^5$，且所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。只有当你解决了本题的所有版本后，才可以进行 hack。 对手 Axial 和 Nife 又发生了争执，他们决定通过在一棵树上玩游戏来解决争端。 他们得到了一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。每个顶点的初始值为 $0$ 或 $1$。一开始，有两个不同的顶点 $x$ 和 $y$ 的值为 $0$，其它所有顶点的值都为 $1$。 两位玩家轮流行动，Axial 先手。在每一回合，当前玩家从所有值为 $1$ 的点中选择一个顶点 $v$，将其值修改为 $0$。在改变 $v$ 的值之前，记 $c_v$ 为 $v$ 的所有相邻顶点中值为 $0$ 的顶点数量。如果 $c_v=1$，则当前玩家得 1 分；否则，得 0 分。游戏结束时所有顶点的值都为 $0$。 最终，设 Axial 和 Nife 的得分分别为 $p$ 和 $q$。Axial 希望最大化 $p-q$，而 Nife 希望最小化它。假设双方都采取最优策略，要求你计算游戏结束时 $p-q$ 的值。

每组测试数据包含多组测试用例。第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每组测试用例第一行输入三个整数 $n$、$x$ 和 $y$（$2 \le n \le 2 \cdot 10^5$，$1 \le x, y \le n$，$x \ne y$），分别代表树的顶点数和最初值为 $0$ 的两个顶点编号。 接下来 $n-1$ 行，每行输入两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示树上的一条无向边。 保证给定的图是一棵树。 保证所有测试用例中的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出一个整数，表示游戏结束时 $p-q$ 的值。

在以下图示中，蓝色顶点初始为 $0$，白色顶点初始为 $1$。 对第一个样例，初始状态为：  Axial 将顶点 $3$ 改为 $0$，它正好有一个相邻顶点为 $0$，因此 Axial 得 1 分。所以 $p-q=1$。 对第二个样例，初始状态为：  Axial 可以选择将顶点 $2$ 或 $3$ 改为 $0$，都可以得 1 分。随后剩下的顶点有两个邻居为 $0$，Nife 得不到分数。因此 $p-q=1$。 对第三个样例，初始状态为：  只有一种操作：将顶点 $2$ 改为 $0$，它有两个邻居为 $0$，Axial 得不到分数。因此 $p-q=0$。 由 ChatGPT 5 翻译