QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[+2]

# 8948. 报复社会

Statistics

给定一棵以 1 为根的有根树,第 i 个点的父亲是 pi ,其颜色是 coli ,保证 coli{0,1}

Alice 和 Bob 在这棵树上玩游戏。两人轮流操作,Alice 先手。每次操作选取一个点 x ,满足 x=1px 已经被删除,然后把 x 删除。

如果最后一个被删除的点的颜色是 0 则 Alice 胜,否则 Bob 胜。两人都会为了胜利执行最优操作。

给出 T 组数据,对每组数据判断胜者是谁。

输入格式

第一行一个正整数 T ,表示数据组数。每组数据的格式如下:

  • 第一行一个正整数 n
  • 第二行 n1 个正整数 p2,p3,,pn
  • 第三行 n 个非负整数 col1,col2,,coln

输出格式

对每组数据输出一行 AliceBob ,表示胜者。

样例输入

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

数据范围

本题采用子任务捆绑测试。

对于所有数据,保证 1T10000,1n5×105,1pi<i,0coli1

Subtask 1 (20 pts): 保证 T=1,n20

Subtask 2 (30 pts): 保证对于所有 i ,满足 i=1pi=1ppi=1

Subtask 3 (20 pts): 保证对于所有 i ,要么 i 是叶子,要么 i 的子树大小为偶数。

Subtask 4 (30 pts): 无特殊限制。