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≤104t \le 10^4, n≤2⋅105n \le 2 \cdot 10^5 and the sum of nn over all test cases does not exceed 2⋅1052 \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 nn vertices numbered from 11 to nn. Each vertex contains either 00 or 11. Initially, two distinct vertices xx and yy contain 00, and all other vertices contain 11.

The players take turns, with Axial going first. On each turn, the current player chooses a vertex vv containing 11 and changes its value to 00. Before changing the value of vv, let cvc_v be the number of neighbors of vv that contain 00. If cv=1c_v = 1, the current player gets one point. Otherwise, they get no points. The game ends when all vertices contain 00.

Let pp and qq be the final scores of Axial and Nife, respectively. Axial wants to maximize p−qp - q, while Nife wants to minimize it. Assuming both players play optimally, determine the value of p−qp - q at the end of the game.

这是该问题的困难版本。两个版本的区别在于,在本版本中,t≤104t \le 10^4,n≤2⋅105n \le 2 \cdot 10^5,且所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。仅当您已解决该问题的所有版本时,才可进行 Hack。

对手 Axial 和 Nife 再次发生争执,他们决定通过在一棵树上玩游戏来解决分歧。

他们被给定一棵包含 nn 个顶点的树,顶点编号为 11 到 nn。每个顶点的值为 00 或 11。初始时,两个互异的顶点 xx 和 yy 的值为 00,其余所有顶点的值均为 11。

双方轮流行动,Axial 先手。在每一轮中,当前玩家选择一个值为 11 的顶点 vv,并将其值更改为 00。在更改 vv 的值之前,设 cvc_v 表示 vv 的邻接顶点中值为 00 的顶点个数。若 cv=1c_v = 1,则当前玩家得一分;否则不得分。当所有顶点的值均为 00 时,游戏结束。

设 pp 和 qq 分别为 Axial 和 Nife 的最终得分。Axial 希望最大化 p−qp - q,而 Nife 希望最小化 p−qp - q。假设双方均采取最优策略,求游戏结束时 p−qp - q 的值。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains three integers nn, xx, and yy (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5, 1≤x,y≤n1 \le x, y \le n, x≠yx \ne y) — the number of vertices in the tree and the two vertices that initially contain 00.

Each of the next n−1n - 1 lines contains two integers uu and vv (1≤u,v≤n1 \le u, v \le n, u≠vu \ne v), denoting an edge between vertices uu and vv.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052 \cdot 10^5.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 nn、xx 和 yy(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5,1≤x,y≤n1 \le x, y \le n,x≠yx \ne y)—— 分别表示树中顶点的数量以及初始时含有 00 的两个顶点。

接下来的 n−1n - 1 行每行包含两个整数 uu 和 vv(1≤u,v≤n1 \le u, v \le n,u≠vu \ne v),表示顶点 uu 与顶点 vv 之间存在一条边。

保证所给图是一棵树。

保证所有测试用例的 nn 值之和不超过 2⋅1052 \cdot 10^5。

输出格式

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

对于每个测试用例,输出一个整数——游戏结束时 p−qp - 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 00, while white vertices initially contain 11.

For the first example, the initial state is:

Axial changes vertex 33 to 00. It has exactly one neighbor containing 00, so Axial gets one point. Therefore, p−q=1p - q=1.

For the second example, the initial state is:

Axial can change either vertex 22 or vertex 33 to 00 and get one point. After that, the remaining vertex has two neighbors containing 00, so Nife gets no points. Therefore, p−q=1p - q=1.

For the third example, the initial state is:

The only possible move is to change vertex 22 to 00. It has two neighbors containing 00, so Axial gets no points. Therefore, p−q=0p - q=0.

在下面的图中,蓝色顶点初始值为 00,白色顶点初始值为 11。

第一个例子的初始状态为:

Axial 将顶点 33 改为 00。该顶点恰好有一个邻居的值为 00,因此 Axial 得 1 分。故 p−q=1p - q = 1。

第二个例子的初始状态为:

Axial 可将顶点 22 或顶点 33 改为 00 并获得 1 分。此后,剩余的那个顶点有两个邻居的值为 00,因此 Nife 得 0 分。故 p−q=1p - q = 1。

第三个例子的初始状态为:

唯一可行的操作是将顶点 22 改为 00。该顶点有两个邻居的值为 00,因此 Axial 得 0 分。故 p−q=0p - q = 0。

输入解题思路,AI测评打分。不知道怎么写?

首页