#1825. 报复社会

    ID: 1825 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1787来源:qoj.ac数据:公开样例树上算法

报复社会

报复社会

题目描述

标题: 报复社会 - Problem - QOJ.ac

#8948. 报复社会

Statistics

给定一棵以 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): 无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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