JZOJ 1350. 游戏

题目

Description

　　Bob经常与Alice一起玩游戏。今天，他们在一棵树上玩游戏。Alice有M1块石子，Bob有M2块石子，游戏一开始，所有石头放在树的节点处，除了树根。Alice先移然后两人轮流移动，每次移动只能选择自己的一个石子，而且只能从当前位置移到父亲节点处，游戏过程中允许一个节点处放多个石子。
　　谁先把自己所有的石子移到树根处谁就失败了，假设两人都是非常聪明，游戏过程中都使用最优策略，给定石子起始位置，要你计算出谁是赢家。

Input

　　输入包含多组测试数据。
　　第一行输入T(T<=10)表示测试数据组数。
　　接下来每组测试数据第一行输入3个整数N(1<=N<=10000)，M1(1<=M1<=10000)，M2(1<=M2<=10000)，其中N表示树的节点数。
　　接下来N-1行描述树，每行包含两个整数A和B(0<=A,B<=N-1)表示树中有一条边连接A,B两点，注意0是树根。
　　接下来一行M1个数，表示Alice的M1个石子的位置。
　　接下来一行M2个数，表示Bob的M2个石子的位置。

Output

　　对于每组测试数据，输出赢家的名字。

Sample Input

Sample Output

Bob
Alice

Data Constraint

Hint

【数据说明】
　　30%的数据满足1<=N<=10,1<=M1,M2<=3

分析

用DFS先把树的深度跑一遍
然后因为每次只能搞一颗
每个点深度乘上个数得到两个人的值
比较大小即可

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define N 10005
 6 using namespace std;
 7 
 8 int p,q;
 9 int i,j,n,m1,m2,l,u,v,ans_A,ans_B;
10 int s1[N],s2[N],d[N];
11 bool vis[N];
12 
13 int next[N*2],list[N],to[N*2];
14 
15 void add(int x) {
16     next[++l]=list[x];
17     list[x]=l;
18 }
19 
20 void dfs(int x) {
21     for (int t=list[x],y=to[t];t;t=next[t],y=to[t]) {
22         if (!vis[y]) {
23             vis[y]=true; d[y]=d[x]+1; dfs(y);
24         }
25     }
26 }
27 
28 int main()
29 {
30     scanf("%d",&p);
31     for (q=1;q<=p;q++) {
32     scanf("%d%d%d",&n,&m1,&m2);
33     l=0;
34     memset(list,0,sizeof(list));
35     for (i=1;i<=n-1;i++) { 
36      scanf("%d%d",&u,&v);
37      to[i*2-1]=v; add(u);
38      to[i*2]=u; add(v);
39     }
40     for (i=1;i<=m1;i++)
41      scanf("%d",&s1[i]);
42     for (i=1;i<=m2;i++)
43      scanf("%d",&s2[i]);   
44     memset(vis,false,sizeof(vis));
45     vis[0]=true;  
46     dfs(0);
47     ans_A=ans_B=0;
48     for (i=1;i<=m1;i++)
49      ans_A+=d[s1[i]];
50     for (i=1;i<=m2;i++)
51      ans_B+=d[s2[i]];
52     if (ans_A>ans_B) printf("Alice
");
53     else printf("Bob
");
54     }
55 }