QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 8948. 报复社会

Statistics

给定一棵以 $1$ 为根的有根树,第 $i$ 个点的父亲是 $p_i$ ,其颜色是 $col_i$ ,保证 $col_i\in \{0,1\}$。

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

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

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

输入格式

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

  • 第一行一个正整数 $n$ 。
  • 第二行 $n-1$ 个正整数 $p_2,p_3,\cdots,p_n$ 。
  • 第三行 $n$ 个非负整数 $col_1,col_2,\cdots,col_n$ 。

输出格式

对每组数据输出一行 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

数据范围

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

对于所有数据,保证 $1\le T\le 10000, 1\le \sum n\le 5\times 10^5, 1\le p_i\lt i, 0\le col_i\le 1$ 。

Subtask $1$ ($20$ pts): 保证 $T=1, n\le 20$ 。

Subtask $2$ ($30$ pts): 保证对于所有 $i$ ,满足 $i=1\lor p_i=1\lor p_{p_i}=1$ 。

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

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