题意描述

Bob经常与Alice一起玩游戏。

今天，他们在一棵树上玩游戏。Alice有$M_1$块石子，Bob有$M_2$块石子.

游戏一开始，所有石头放在树的节点处，除了树根。

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

谁先把自己所有的石子移到树根处谁就失败了。

现在假设两人都是非常聪明，游戏过程中都使用最优策略，给定石子起始位置，要你计算出谁是赢家。

输入格式

输入包含多组测试数据。

第一行输入$t$，表示测试数据组数。

接下来每组测试数据第一行输入$3$个整数$N$，$M_1$，$M_2$，其中$N$表示树的节点数。

接下来$N-1$行描述树，每行包含两个整数$A$和$B$,表示树中有一条边连接$A,B$两点，注意$0$是树根。

接下来一行$M_1$个数，表示Alice的$M_1$个石子的位置。

接下来一行$M_2$个数，表示Bob的$M_2$个石子的位置。

输出格式

输出包括$t$行，对于每组测试数据，输出赢家的名字。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

Bob
Alice

数据范围与约定

对于$30\%$的数据，保证$1 \leq N \leq 10$ , $1 \leq M1,M2 \leq 3$

对于$100\%$的数据，保证$1 \leq t \leq 10$，$1 \leq N \leq 10^4$ ，$1 \leq M1,M2 \leq 10^4$

分析

考场上第一眼以为是道神仙博弈论，结果发现是道结论题……

不难发现，玩家将其所有石子移向根节点所需的次数决定了其胜负。而这个次数就是其所有石子的深度之和。

因此我们只要大力搜索一遍，预处理出每个石子在树上的深度，然后比较两人各自的石子深度之和即可。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long 
#define I inline
#define N 100001

using namespace std;

int n , m1 , m2 , deep[N];
int Alice[N] , Bob[N];

struct Edge{
    int from;
    int to;
    int last;
}edge[N << 1];

int edge_num;
int head[N << 1];

I void add_edge(int from , int to){
    edge[++ edge_num] = (Edge){from , to , head[from]};
    head[from] = edge_num;
}

bool vis[N];

void search(int root , int fa , int dep){
	deep[root] = dep;
    for(int i = head[root]; i ; i = edge[i].last){
        int to = edge[i].to;
        if(to == fa){
            continue;
        }
        search(to , root , dep + 1);
    }
}

namespace Solve{    //方便处理多组数据

    void main(){
        for(int i = 1; i <= n; i ++){   //多测不清空，爆零两行泪
            Alice[i] = Bob[i] = 0;
			vis[i] = false;
            edge[i].to = edge[i].last = edge[i].from = 0;
        }
        memset(head , 0 , sizeof(head));
        edge_num = 0;
        int u , v;
        cin >> n >> m1 >> m2;
        for(int i = 1; i <= n - 1; i ++){
            cin >> u >> v;
            u ++ , v ++;    //由于题目中将0作为根节点，因此读入时需要+1以方便处理
            add_edge(u , v);
            add_edge(v , u);
        }
        search(1 , 0 , 0);  //预处理各个点的深度
        ll A = 0 , B = 0;
        for(int i = 1; i <= m1; i ++){  //计算两个人的权值
            cin >> Alice[i];
            Alice[i] += 1;
            A += deep[Alice[i]];
        }
        for(int i = 1; i <= m2; i ++){
            cin >> Bob[i];
            Bob[i] += 1;
            B += deep[Bob[i]];
        }
        if(A > B) puts("Alice");    //若先手的次数大于后手，则先手必胜
        else puts("Bob");   //否则，后手必胜。
    }
}


int main(){
    int t;
    cin >> t;
    while(t --){
        Solve :: main();
    }
    return 0;
}