我這次只負責出一題水題，因為我太弱ㄌ

這題賽中只有一個人AC，連部分分都只有一個人拿

我猜是放在 pD 的關係，就跟你們說沒按難度排ㄌ

題敘

TL/ML: 1s/256mb

給你一棵有根樹，每個節點有一個給定的布林值
你每次操作可以把以某個節點為根的子樹取反
求至少需要幾次操作使的所有值均為 $0$

輸入限制

$ n \leq 5 \times 10^5$

Subtasks

  1. $n \leq 20$ (20%)
  2. 樹是一顆星 (31%)
  3. 無額外限制 (49%)

題解

Subtask 1

就暴力，沒啥好說ㄉ

bool b[maxn], tr[maxn];
vector <int> adj[maxn];
void dfs(int x){
    for (auto i:adj[x]){
        tr[i] ^= tr[x];
        dfs(i);
    }
}

void solve(){
    int n;

    cin >> n;
    REP0(i, n){
        char c;

        cin >> c;
        b[i] = (c == 'B');
    }
    for (int i=1;i<n;++i){
        int p;

        cin >> p;
        adj[p-1].pb(i);
    }
    int ans = n+1;
    REP0(mask, 1<<n){
        REP0(i, n) tr[i] = ((mask >> i) & 1);
        dfs(0);
        bool ok = true;
        REP0(i, n) if (b[i] ^ tr[i]){
            ok = false;
            break;
        }
        if (ok) ans = min(ans, __builtin_popcount(mask));
    }
    cout << ans;
}

$O(n2^n)$ AC

Subtask 2

給的樹是一顆星

只需要考慮根解點有被選擇跟沒被選擇就好了

這31分真的很好拿，沒拿很可惜QQ

Subtask 3(滿分)

滿分解的部分有三種作法

  1. Bottom-Up DP
  2. Top-Down DP
  3. 觀察

其實都是 $O(n)$ 所以只有常數差距而已

以下一個一個講

Bottom-Up DP

我們可以定義出一個 DP 式 $$dp[i][0/1]$$ 分別表示使以 $i$ 為根的子樹全部都是 $0/1$ 所需的最少操作

而轉移式也可以列出來為

$$\displaystyle dp[i][0] = \begin{cases} \sum_{j \in son_i} dp[j][0], & \text{if } color_i \text{ is 0.} \\ 1 + \sum_{j \in son_i} dp[j][1], & \text{otherwise} \end{cases}$$ $$\displaystyle dp[i][1] = \begin{cases}1 + \sum_{j \in son_i} dp[j][0], & \text{if } color_i \text{ is 0.} \\ \sum_{j \in son_i} dp[j][1], & \text{otherwise} \end{cases}$$

最後 $dp[1][0]$ 就會是答案了

Top-Down DP

我們可以發現，根節點的狀態只能被他自己改變

因此我們可以採用另一個更接近greedy的策略

從根節點開始 dfs，只要遇到黑色就選取以該節點為根的子樹

可以證明這樣 greedy 的結果跟前面 DP 是一樣的

The proof is left as an exercise for the reader.(X

觀察

這上面的寫法都還需要跑一次 dfs，太慢ㄌ

我們再觀察 Top-Down 的過程，你會發現其實除了根節點，只要一個節點跟他的父節點顏色不同就會被選取到

而根節點只要是黑色就會被選

因此我們其實只需要判斷這件事就足夠了

程式碼可以短成這樣

bool b[maxn];

void solve(){
    int n;

    cin >> n;
    REP1(i, n){
        char c;

        cin >> c;
        b[i] = (c == 'B');
    }
    int ans = b[1];
    for (int i=2;i<=n;++i){
        int p;

        cin >> p;
        ans += (b[i] ^ b[p]);
    }
    cout << ans << '\n';
}

於是你就獲得ACㄌ

就說是水題QQ