/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
頂点に 1 から N の番号がついた N 頂点の根付き木が与えられます。頂点 1 が根であり、頂点 i\ (2\leq i \leq N) の親は P_i です。
根付き木の何個かの頂点には 0 以上 N 以下の整数が書かれています。この情報は数列 A=(A_1,A_2,\ldots,A_N) で与えられ、A_i \neq -1 の場合頂点 i に整数 A_i が書かれており、A_i=-1 の場合頂点 i には整数が書かれていないことを意味しています。
Alice と Bob でゲームをします。Alice が先手で、全ての頂点に整数が書かれるまで以下の操作を交互に繰り返します。
- 整数が書かれていない頂点を 1 個選び、 0 以上 N 以下の整数を書く。
操作終了後の各頂点 v に対して、 f(v) を「頂点 v の部分木に含まれるどの頂点（v 含む）にも書かれていないような最小の非負整数」と定めます。
f(v) = K を満たす頂点 v が存在する場合 Alice の勝利、そうでない場合 Bob の勝利となります。両者が最適な行動を行う場合、どちらが勝つか判定してください。
T 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- 1 \leq T \leq 10^3
- 2 \leq N \leq 10^3
- 0 \leq K \leq N
- 1 \leq P_i < i\ (2\leq i\leq N)
- -1 \leq A_i \leq N\ (1\leq i\leq N)
- 入力される数値は全て整数
- 1 つの入力に含まれるテストケースについて、N の総和は 2\times 10^3 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各ケースは以下の形式で与えられる。
N K P_2 P_3 \ldots P_N A_1 A_2 \ldots A_N
出力
T 行出力せよ。i\ (1\leq i \leq T) 行目には、 i 番目のテストケースについて、両者が最適な行動を行う場合 Alice が勝つならば Alice を、Bob が勝つならば Bob を出力せよ。
入力例 1
2 4 2 1 1 2 -1 -1 3 1 6 4 1 2 2 1 3 -1 -1 -1 -1 -1 -1
出力例 1
Alice Bob
1 番目のテストケースについては、Alice が頂点 2 に 0 を書き込むと、Bob の操作に依らず f(2) = 2 となります。そのため、Alice は勝つことができます。
2 番目のテストケースについては、Bob が上手く書き込む整数を選ぶことで、 f(v) = 4 なる頂点が存在しないようにできます。
Score : 500 points
Problem Statement
You are given a rooted tree with N vertices numbered 1 to N. Vertex 1 is the root, and the parent of vertex i\ (2\leq i \leq N) is P_i.
Some vertices of the rooted tree have non-negative integers from 0 to N written on them. This information is given by the sequence A=(A_1,A_2,\ldots,A_N). If A_i \neq -1, vertex i has the integer A_i written on it; if A_i=-1, vertex i does not have an integer written on it.
Alice and Bob play a game. Alice goes first, and they take turns performing the following operation until all vertices have an integer written on them.
- Choose one vertex without an integer written on it and write a non-negative integer between 0 and N on it.
After the operations, for each vertex v, let f(v) be the smallest non-negative integer not written on any vertex (including v) in the subtree rooted at vertex v.
If there is a vertex v such that f(v) = K, Alice wins. Otherwise, Bob wins. Determine the winner when both players play optimally.
There are T test cases. Answer each of them.
Constraints
- 1 \leq T \leq 10^3
- 2 \leq N \leq 10^3
- 0 \leq K \leq N
- 1 \leq P_i < i\ (2\leq i\leq N)
- -1 \leq A_i \leq N\ (1\leq i\leq N)
- All input values are integers.
- The sum of N over all test cases in a single input is at most 2\times 10^3.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is given in the following format:
N K P_2 P_3 \ldots P_N A_1 A_2 \ldots A_N
Output
Print T lines. The i-th (1\leq i \leq T) line should contain Alice if Alice wins, and Bob if Bob wins when both players play optimally in the i-th test case.
Sample Input 1
2 4 2 1 1 2 -1 -1 3 1 6 4 1 2 2 1 3 -1 -1 -1 -1 -1 -1
Sample Output 1
Alice Bob
In the first test case, if Alice writes 0 on vertex 2, then f(2) = 2 regardless of Bob's operation. Therefore, Alice can win.
In the second test case, Bob can ensure that there will be no vertex with f(v) = 4 by choosing the right integer to write.