[图论]游戏

题目描述

$B$ 经常与 $A$ 一起玩游戏。今天，他们在一棵树上玩游戏。$A$ 有 $m1$ 块石子，$B$ 有 $m2$ 块石子，游戏一开始，所有石头放在树的节点处，除了树根。

$A$ 先移动石子。然后两人轮流移动，每次移动只能选择自己的一个石子，而且只能从当前位置移到父亲节点处，游戏过程中允许一个节点处放多个石子。

谁先把自己所有的石子移到树根处谁就失败了，假设两人都是非常聪明，游戏过程中都使用最优策略，给定石子起始位置，要你计算出谁是赢家。

为了简化题目，假设树根为 $0$。

输入格式

输入包含多组测试数据。

第一行输入 $T$ 表示测试数据组数。
接下来每组测试数据第一行输入 $3$ 个整数 $n$,$m1$,$m2$，$n$ 为树的节点个数。
接下来 $n-1$ 行，每行包含两个整数 $x，y$$(0\le x,y<n)$，表示树中有一条边连接 $x$ 和 $y$。
接下来 $m1$ 行，每行一个整数，表示 $A$ 的石子的位置。
接下来 $m2$ 行，每行一个整数，表示 $B$ 的石子的位置。

输出格式

对于每组数据，输出 $A$ 或 $B$ 表示 $A$ 或 $B$ 赢了。

数据范围

对于 $30\%$ 的数据，$1\le n\le 10$，$1\le m1,m2\le n$。
对于 $100\%$ 的数据，$1\le n\le 10^4$，$1\le m1,m2\le 10^4$。

样例

输入：

2
3 1 1
0 1
2 0
1
2
3 2 1
0 1
1 2
2 2
2

输出：

B
A

思路

首先一眼看上去，似乎是个博弈题，但其实只是简单的树。

石子只能移到其根节点，且根节点只有一个，因此每个石子移到根节点的距离就能求出来。
将 $A$ 和 $B$ 的每个石子离根节点的距离求出来相加，进行比较。

$A$ 为先手，只有 $su{m}_A>su{m}_B$ 时，$A$ 才能赢，否则 $B$ 赢。

比如 $su{m}_A=su{m}_B=1$，$A$ 先走，$B$ 再走，$A$ 就不能走了，$B$ 赢。

代码

#include<bits/stdc++.h>
using namespace std;
int T;
int n, m1, m2;
int dep[100010];//深度
int a[100010], b[100010];
vector<int> v[100010];//图
//x：当前节点 y:父亲节点 z:当前节点深度
void dfs(int x, int y, int z){dep[x] = z;for(auto i : v[x]){if(i == y){//父亲continue;}dfs(i, x, z + 1);}
}
int main(){scanf("%d", &T);while(T --){//多组数据清空memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));memset(dep, 0, sizeof(dep));scanf("%d %d %d", &n, &m1, &m2); for(int i = 1; i < n; ++ i){int x, y;scanf("%d %d", &x, &y);v[x].push_back(y);v[y].push_back(x);}//将 a和b 每个位置的石子个数统计出来，方便以后计算for(int i = 1; i <= m1; ++ i){int x;scanf("%d", &x);a[x] ++;}for(int i = 1; i <= m2; ++ i){int x;scanf("%d", &x);b[x] ++;}//dfs 计算每个节点的深度dfs(0, -1, 0);int sum1 = 0, sum2 = 0;for(int i = 1; i <= n; ++ i){sum1 += a[i] * dep[i];}for(int i = 1; i <= n; ++ i){sum2 += b[i] * dep[i];}if(sum1 > sum2){printf("A\n");}else{printf("B\n");	}//v 在清空时注意要把 0 清了for(int i = 0; i <= n; ++ i){v[i].clear();}}return 0;
}