FAFUOJ 1572 Big Castle 樹形 DP (狀態壓縮)

問題

給定一棵樹，每個節點初始狀態 0/1。操作：選一節點翻轉自身及所有鄰居。問能否使所有節點變為 1。n ≤ 50000。

樹形 DP 狀態定義

`dp[u][val][flipped]`：以 u 為根的子樹，u 最終值為 `val` (0/1)，u 是否被父節點操作翻轉過 (`flipped` 0/1)，是否可行。
葉節點基礎情況直接由初始值與翻轉狀態決定。
內部節點合併子節點狀態：統計子節點可能的 (val, flipped) 組合，根據奇偶性判斷 u 能否達成目標值。

核心合併邏輯

void dfs(int u, int p) {
    // 統計子節點四種狀態計數
    int odd1=0, even1=0, both1=0; // flipped=0 時子節點 val=0/1/both 可行數
    int odd2=0, even2=0, both2=0; // flipped=1 時...
    for (v : children) {
        dfs(v,u);
        // 根據 dp[v][0][0], dp[v][1][0] 歸類...
    }
    // 推導 dp[u][*][*] 可行性
    // 關鍵：子節點翻轉狀態由 u 是否操作決定
}

最終判斷

根節點無父節點，故 `flipped=0`。若 `dp[1][1][0] || dp[1][1][1]` 為真 → "Great Cdfpysw!"，否則 "Poor Nanaya!"。

複雜度

O(n) 時間，每節點常數狀態合併。空間 O(n)。遞歸深度可能大，需增棧或改迭代。