ProblemB Binary Tree (水題)

題目大意：

給 ALICE and BOB 一個遊戲，這個遊戲是他們要不斷刪除樹的節點，但有規定，刪除的節點必定是完整二元樹。試問，誰一定必勝？

完整二元樹定義：

1. root 必須要有 left node and right node
2. 是樹的最後節點

分析：

雖然叫水題，但是卻沒辦法解出來，假水題阿 QQ
然後香港的題目真的好難，第一題我用 20 min 都無法想出來，於是我觀察別人的 Blog 才能將此題解出。

此題可以用奇偶數可以直接判斷 Alice and Bob 誰是贏家！很神奇吧

為甚麼呢？
因為 ALICE 與 BOB 都只能砍掉「完整二元樹」，而在這裏的完整二元樹節點都會是「奇數」，完整二元樹的樹節點必定是 1 , 3 , 5 , 7 …..。然後透過數學歸納我們可以歸納出兩個奇數 (ALICE and BOB 各畫一次 )相加必等於偶數。

於是當「節點」為奇數時必定是 ALICE 勝，因為接下來換 BOB，但如果 BOB 可以畫就必定是偶數。
反之，當「節點」為偶數時必定是 BOB 勝，由前句推出

P.S. 觀看此 Blog 才學習到的
小小的題外話，我可以在 cin >> n 時即可輸出答案，不一定要等到將這筆測資完整 cin 完全時在輸出。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;

int main()
{
    int t ;
    cin >> t ;
    while(t--){
        int a , b , n ;
        cin >> n ;
        if(n % 2)
            cout << "Alice\n" ;
        else
            cout << "Bob\n" ;
        for(int i = 1 ; i < n ; i++){
            cin >> a >> b ;
        }
    }
    return 0;
}