CF2271H1.Personal Issues (Easy Version)
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is the easy version of the problem. The difference between the versions is that in this version, t≤1000, n≤3000 and the sum of n over all test cases does not exceed 3000. 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≤1000,n≤3000,且所有测试用例的 n 之和不超过 3000。仅当您已解决该问题的所有版本时,才可进行 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≤1000). The description of the test cases follows.
The first line of each test case contains three integers n, x, and y (2≤n≤3000, 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 3000.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤1000)。随后是各测试用例的描述。
每个测试用例的第一行包含三个整数 n、x 和 y(2≤n≤3000,1≤x,y≤n,x=y)—— 分别表示树中顶点的数量以及初始时含有 0 的两个顶点。
接下来的 n−1 行每行包含两个整数 u 和 v(1≤u,v≤n,u=v),表示顶点 u 与顶点 v 之间存在一条边。
保证所给图是一棵树。
保证所有测试用例的 n 值之和不超过 3000。
输出格式
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测评打分。不知道怎么写?