CF2271H2.Personal Issues (Hard Version)
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is the hard version of the problem. The difference between the versions is that in this version, t≤104, n≤2⋅105 and the sum of n over all test cases does not exceed 2⋅105. 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 cv be the number of neighbors of v that contain 0. If cv=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.
这是该问题的困难版本。两个版本的区别在于,在本版本中,t≤104,n≤2⋅105,且所有测试用例的 n 之和不超过 2⋅105。仅当您已解决该问题的所有版本时,才可进行 Hack。
对手 Axial 和 Nife 再次发生争执,他们决定通过在一棵树上玩游戏来解决分歧。
他们被给定一棵包含 n 个顶点的树,顶点编号为 1 到 n。每个顶点的值为 0 或 1。初始时,两个互异的顶点 x 和 y 的值为 0,其余所有顶点的值均为 1。
双方轮流行动,Axial 先手。在每一轮中,当前玩家选择一个值为 1 的顶点 v,并将其值更改为 0。在更改 v 的值之前,设 cv 表示 v 的邻接顶点中值为 0 的顶点个数。若 cv=1,则当前玩家得一分;否则不得分。当所有顶点的值均为 0 时,游戏结束。
设 p 和 q 分别为 Axial 和 Nife 的最终得分。Axial 希望最大化 p−q,而 Nife 希望最小化 p−q。假设双方均采取最优策略,求游戏结束时 p−q 的值。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains three integers n, x, and y (2≤n≤2⋅105, 1≤x,y≤n, x=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≤u,v≤n, u=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⋅105.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例的第一行包含三个整数 n、x 和 y(2≤n≤2⋅105,1≤x,y≤n,x=y)—— 分别表示树中顶点的数量以及初始时含有 0 的两个顶点。
接下来的 n−1 行每行包含两个整数 u 和 v(1≤u,v≤n,u=v),表示顶点 u 与顶点 v 之间存在一条边。
保证所给图是一棵树。
保证所有测试用例的 n 值之和不超过 2⋅105。
输出格式
For each test case, output a single integer — the value of p−q at the end of the game.
对于每个测试用例,输出一个整数——游戏结束时 p−q 的值。
输入输出样例
输入#1
4 3 1 2 1 2 2 3 4 1 4 1 2 2 3 3 4 3 1 3 1 2 2 3 6 2 3 1 2 1 3 1 4 1 5 1 6
输出#1
1 1 0 0
说明/提示
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.
在下面的图中,蓝色顶点初始值为 0,白色顶点初始值为 1。
第一个例子的初始状态为:

Axial 将顶点 3 改为 0。该顶点恰好有一个邻居的值为 0,因此 Axial 得 1 分。故 p−q=1。
第二个例子的初始状态为:

Axial 可将顶点 2 或顶点 3 改为 0 并获得 1 分。此后,剩余的那个顶点有两个邻居的值为 0,因此 Nife 得 0 分。故 p−q=1。
第三个例子的初始状态为:

唯一可行的操作是将顶点 2 改为 0。该顶点有两个邻居的值为 0,因此 Axial 得 0 分。故 p−q=0。
输入解题思路,AI测评打分。不知道怎么写?