给定一棵以 1 为根的有根树,第 i 个点的父亲是 pi ,其颜色是 coli ,保证 coli∈{0,1}。
Alice 和 Bob 在这棵树上玩游戏。两人轮流操作,Alice 先手。每次操作选取一个点 x ,满足 x=1 或 px 已经被删除,然后把 x 删除。
如果最后一个被删除的点的颜色是 0 则 Alice 胜,否则 Bob 胜。两人都会为了胜利执行最优操作。
给出 T 组数据,对每组数据判断胜者是谁。
输入格式
第一行一个正整数 T ,表示数据组数。每组数据的格式如下:
- 第一行一个正整数 n 。
- 第二行 n−1 个正整数 p2,p3,⋯,pn 。
- 第三行 n 个非负整数 col1,col2,⋯,coln 。
输出格式
对每组数据输出一行 Alice
或 Bob
,表示胜者。
样例输入
3 2 1 1 0 5 1 2 2 1 0 0 0 1 0 8 1 2 2 2 1 6 1 1 0 0 0 1 0 1 0
样例输出
Alice Bob Alice
数据范围
本题采用子任务捆绑测试。
对于所有数据,保证 1≤T≤10000,1≤∑n≤5×105,1≤pi<i,0≤coli≤1 。
Subtask 1 (20 pts): 保证 T=1,n≤20 。
Subtask 2 (30 pts): 保证对于所有 i ,满足 i=1∨pi=1∨ppi=1 。
Subtask 3 (20 pts): 保证对于所有 i ,要么 i 是叶子,要么 i 的子树大小为偶数。
Subtask 4 (30 pts): 无特殊限制。