1451 . 樹上遊戲
TopCoder
Tags
Description
這次 Alice 與 Bob 在一棵有根樹上玩遊戲，這棵有根樹有 $N$ 個節點，以 $1$ 為根，每個節點上都有可能擺放著若干顆棋子。
遊戲的進行方式如下，雙方輪流進行，由 Alice 先手，每次輪到一位玩家時，他可以從樹上選擇一些棋子（只要非零即可，也可以在一個節點上有多個棋子時只拿其中幾顆），並對每一個棋子做以下操作：
- 如果該棋子所在的節點為葉子，將其移出樹中。
- 如果該棋子所在的節點不是葉子，將其移動到該節點的任何一個直接連接的小孩上。
當輪到一位玩家時，找不到任何棋子可以選擇的那位就輸了。現在給你一個遊戲盤面，包含有根樹的長相、以及每個節點上是否存放著棋子的資訊，請問在 Alice 跟 Bob 皆絕頂聰明的情況下，誰有必勝策略？
注意，在本題給定的初始盤面中，每個節點上至多只會有一個棋子，但遊戲過程中依然有可能會出現棋子重疊在一個節點上的情況。
Input Format
本題有多筆測資，輸入首行會有一個正整數 $T$，代表測資筆數。
對於每一筆測資，輸入首行會有一個正整數 $N$，代表有根樹的節點數量。
次行會有一個長度為 $N$ 的 01 字串 $s_1s_2\cdots s_N$，代表每個節點上是否存放著一顆棋子。更詳細地說，若 $s_i$ 為 0，則節點 $i$ 沒有棋子；若 $s_i$ 為 1，則節點 $i$ 有棋子。
第三行會有 $N-1$ 個正整數 $p_2, p_3, \ldots, p_N$，代表節點 $i$ 的父節點編號為 $p_i$。
- $1\le T\le 10^ 5$
- $1\le N\le 3\times 10^ 5$
- $s$ 是一個長度為 $N$ 的
01字串 - 保證輸入為一合法以 $1$ 為根的有根樹
- 所有測資的 $N$ 之總和不會超過 $3\times 10^ 5$
Output Format
對於每一筆測資，若給定的遊戲盤面為先手必勝，輸出 Alice，否則輸出 Bob。
Sample Input 1
4 2 10 1 2 11 1 4 1010 1 1 3 1 0
Sample Output 1
Bob Alice Alice Bob
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 1~21 | 初始盤面只會有一個棋子。 | 40 |
| 3 | 0~45 | 無特別限制。 | 60 |