洛谷P8127 [BalticOI 2021 Day2] The Xana coup 題解 樹形DP

題目連結：​​https://www.luogu.com.cn/problem/P8127​​

題目大意：給定一棵包含 \(n\) 個節點的樹，樹上每個點都有一個權值，節點 \(i\) 的權值為 \(a_i(a_i \in \{0,1\})\)。每次可以選擇樹上一個點，将這個點以及與其相鄰的所有點的權值取反（\(0\) 變成 \(1\)，\(1\) 變成 \(0\)）。問：最少需要幾次操作能夠讓樹上所有點的權值都變為 \(0\)？

我的思路：

首先是樹形DP，每個節點 \(u\) 對應 \(4\)

• \(f_{u,0}\) 表示節點權值為 \(0\)，沒有對節點進行操作時對應的最小操作次數；
• \(f_{u,1}\) 表示節點權值為 \(1\)，沒有對節點進行操作時對應的最小操作次數；
• \(f_{u,2}\) 表示節點權值為 \(0\)，有對節點進行操作時對應的最小操作次數；
• \(f_{u,3}\) 表示節點權值為 \(1\)，有對節點進行操作時對應的最小操作次數。

上述所有狀态（即 \(f_{u,0},f_{u,1},f_{u,2},f_{u,3}\)）因為對于節點 \(u\) 的非子孫節點來說，它們是沒有辦法修改節點 \(u\) 的子孫節點的狀态的，是以所有的 \(f_{u,i}(0 \le i \le 3)\) 對應的狀态還包含的一個資訊是 —— 節點 \(u\) 的所有子孫節點目前的權值都為 \(0\)。

同時，這些操作都不考慮父節點的影響（因為我這裡的狀态都是根據子節點的狀态推導目前節點的狀态）。

除此之外，我用 \(f_{u,i} = +\infty\) 來表示狀态 \(f_{u,i}\)

然後就可以推導所有的狀态了。

葉子節點

對于葉子節點 \(u\)

• 如果 \(a_u = 1\)（也就是原始節點的權值為 \(1\)），則：

• \(f_{u,0} = +\infty\)（因為葉子節點不操作的話無法讓節點權值變成 \(0\)）
• \(f_{u,1} = 0\)（因為本身節點權值就為 \(1\)）
• \(f_{u,2} = 1\)（因為操作一次恰好讓節點權值變成 \(0\)）
• \(f_{u,3} = +\infty\)（因為操作一次之後節點權值變成了 \(0\)，而不是 \(1\)）

• 如果 \(a_u = 0\)（也就是原始節點的權值為 \(0\)），則：

• \(f_{u,0} = 0\)（因為本身節點權值就為 \(0\)）
• \(f_{u,1} = +\infty\)（因為葉子節點不操作的話無法讓節點權值變成 \(1\)）
• \(f_{u,2} = +\infty\)（因為操作一次之後節點權值變成了 \(1\)，而不是 \(0\)）
• \(f_{u,3} = 1\)（因為操作一次恰好讓節點權值變成 \(1\)）

非葉子節點

對于目前節點 \(u\)

• 如果選擇不操作，則它的子節點的狀态必須都是 \(0\)（設子節點為 \(v\)，則此時隻跟 \(f_{v,0}\)、\(f_{v,2}\)
• 如果選擇操作，則它的子節點的狀态必須都是 \(1\)（設子節點為 \(v\)，則此時隻跟 \(f_{v,1}\)、\(f_{v,3}\)

但是這裡有一個需要思考的問題，就是：目前節點 \(u\)

影響主要在于 —— 子節點中操作過的點是奇數個還是偶數個。

是以可以額外定義四個狀态：\(g_{i,0}, g_{i,1}, h_{i,0}, h_{i,1}\)，這四個狀态是對于目前節點 \(u\) 來說的。對于目前節點 \(u\)，設其有 \(m\)

• \(g_{i,0}\) 表示節點 \(u\) 的前 \(i\) 個子節點全都是 \(0\) 且有偶數個操作過時對應的最少操作次數（偶數個操作過相當于對節點 \(u\) 的狀态沒影響，奇數個操作過就會對節點 \(u\)
• \(g_{i,1}\) 表示節點 \(u\) 的前 \(i\) 個子節點全都是 \(0\)
• \(h_{i,0}\) 表示節點 \(u\) 的前 \(i\) 個子節點全都是 \(1\)
• \(h_{i,1}\) 表示節點 \(u\) 的前 \(i\) 個子節點全都是 \(1\)

首先：

• \(g_{0,0} = h_{0,0} = 0\)
• \(g_{0,1} = h_{0,1} = +\infty\)

其次，當 \(i \gt 0\) 時，（設節點 \(u\) 的第 \(i\) 個子節點為 \(v\)，則）有：

• \(g_{i,0} = \min \{ g_{i-1,0} + f_{v,0}, g_{i-1,1} + f_{v,2} \}\)
• \(g_{i,1} = \min \{ g_{i-1,0} + f_{v,2}, g_{i-1,1} + f_{v,0} \}\)
• \(h_{i,0} = \min \{ h_{i-1,0} + f_{v,1}, h_{i-1,1} + f_{v,3} \}\)
• \(h_{i,1} = \min \{ h_{i-1,0} + f_{v,3}, h_{i-1,1} + f_{v,1} \}\)

當然我們需要的隻有最終計算出來的 \(g_{m,0}, g_{m,1}, h_{m,0}, h_{m,1}\) 這四個狀态（其中 \(m\) 是目前節點 \(u\)

此時再分别讨論 \(a_u\) 是 \(1\) 還是 \(0\)

當 \(a_u = 1\)

• \(f_{u,0} = g_{m,1}\)（因為本身是 \(1\) 且不操作，要變成 \(0\)，是以需要子節點中是 \(0\)
• \(f_{u,1} = g_{m,0}\)（因為本身就是 \(1\) 且不操作，是以需要子節點中是 \(0\)
• \(f_{u,2} = 1 + h_{m,0}\)（因為本身是 \(1\)，操作一次自己變成 \(0\)，是以需要子節點是 \(1\)
• \(f_{u,3} = 1 + h_{m,1}\)（因為本身是 \(1\)，操作一次會變成 \(0\)，是以需要子節點是 \(1\)

當 \(a_u = 0\)

• \(f_{u,0} = g_{m,0}\)（因為本身是 \(0\) 且不操作，是以需要子節點中是 \(0\)
• \(f_{u,1} = g_{m,1}\)（因為本身是 \(0\) 且不操作，要變成 \(1\)，是以需要子節點中是 \(0\)
• \(f_{u,2} = 1 + h_{m,1}\)（因為本身是 \(0\)，操作一次會變成 \(1\)，是以需要子節點是 \(1\)
• \(f_{u,3} = 1 + h_{m,0}\)（因為本身是 \(0\)，操作一次自己變成 \(1\)，是以需要子節點是 \(1\)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int INF = (1<<29);
int n, a[maxn], f[maxn][4], g[maxn][2], h[maxn][2];
vector<int> e[maxn];

/**
f[u][0] 點權為 0，點未操作
f[u][1] 點權為 1，點未操作
f[u][2] 點權為 0，點有操作
f[u][3] 點權為 1，點有操作
*/

void dfs(int u, int p) {
    int sz = e[u].size();
    if (sz == 1 && u != 1) {    // 葉子節點
        if (a[u] == 1) {
            f[u][0] = INF;
            f[u][1] = 0;
            f[u][2] = 1;
            f[u][3] = INF;
        }
        else {  // a[u] == 0
            f[u][0] = 0;
            f[u][1] = INF;
            f[u][2] = INF;
            f[u][3] = 1;
        }
        return;
    }
    vector<int> tmp;
    for (auto v : e[u])
        if (v != p)
            dfs(v, u), tmp.push_back(v);
    int m = tmp.size();
    g[0][0] = h[0][0] = 0;
    g[0][1] = h[0][1] = INF;
    for (int i = 1; i <= m; i++) {
        int v = tmp[i-1];
        g[i][0] = min(INF, min(g[i-1][0] + f[v][0], g[i-1][1] + f[v][2]));
        g[i][1] = min(INF, min(g[i-1][0] + f[v][2], g[i-1][1] + f[v][0]));
        h[i][0] = min(INF, min(h[i-1][0] + f[v][1], h[i-1][1] + f[v][3]));
        h[i][1] = min(INF, min(h[i-1][0] + f[v][3], h[i-1][1] + f[v][1]));
    }
    if (a[u] == 1) {
        f[u][0] = g[m][1];
        f[u][1] = g[m][0];
        f[u][2] = min(INF, 1 + h[m][0]);
        f[u][3] = min(INF, 1 + h[m][1]);
    }
    else {
        f[u][0] = g[m][0];
        f[u][1] = g[m][1];
        f[u][2] = min(INF, 1 + h[m][1]);
        f[u][3] = min(INF, 1 + h[m][0]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) scanf("%d", a+i);
    dfs(1, -1);
    int ans = min(f[1][0], f[1][2]);
    if (ans == INF) puts("impossible");
    else printf("%d\n", ans);
    return 0;
}