P11018 Monochrome Tree 题解

:::info[Description] Link. :::

:::infoSolution 注意到一个点 $u$ 最多执行一次一类操作和一次二类操作，因此考虑直接树上 dp，设 $f_{i,0/1,0/1}$ 表示当前考虑以 $i$ 结点为根的子树， $i$ 结点的颜色是黑色 / 白色， $i$ 结点被 $1$ 操作覆盖了偶数次 / 奇数次，且使得整个子树内所有结点颜色同色，最少需要花费的操作数量是多少。

转移是容易的，直接对每个子结点分类讨论合并信息即可。把转移推对了就没啥细节。

时间复杂度为 $O(n)$ ，可以通过该题。 :::

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

vector<int> adj[N];
int a[N], f[N][2][2];
inline void dfs(int u, int fa) {
    int g[2][2] = {0, inf, 0, inf}, h[2][2] = {0, 0, 0, 0};
    for (int &v : adj[u]) if (v != fa) {
        dfs(v, u);
        for (int i : {0, 1}) for (int j : {0, 1})
            h[i][j] = min(f[v][i][0] + g[i][j], f[v][i][1] + g[i][j ^ 1]);
        for (int i : {0, 1}) for (int j : {0, 1})
            g[i][j] = h[i][j];
    } 
    if (adj[u].size() == 1 && fa) {
        f[u][a[u]][0] = 0;
        f[u][a[u] ^ 1][0] = 1;
        f[u][a[u]][1] = 2;
        f[u][a[u] ^ 1][1] = 1;
    } else if (a[u]) {
        f[u][0][0] = min(g[1][0] + 1, g[1][1] + 2);
        f[u][0][1] = min(g[0][0] + 1, g[0][1]);
        f[u][1][0] = min(g[1][0], g[1][1] + 1);
        f[u][1][1] = min(g[0][0] + 2, g[0][1] + 1);
        for (int i : {0, 1}) for (int j : {0, 1})
            f[u][i][j] = min(f[u][i][j], f[u][i ^ 1][j] + 1);
    } else {
        f[u][0][0] = min(g[0][0], g[0][1] + 1);
        f[u][0][1] = min(g[1][0] + 2, g[1][1] + 1);
        f[u][1][0] = min(g[0][1] + 2, g[0][0] + 1);
        f[u][1][1] = min(g[1][0] + 1, g[1][1]);
        for (int i : {0, 1}) for (int j : {0, 1})
            f[u][i][j] = min(f[u][i][j], f[u][i ^ 1][j] + 1);
    }
}

inline void sol([[maybe_unused]]int __testcase_id) {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        adj[a].emplace_back(b), adj[b].emplace_back(a);
    } dfs(1, 0);
    if (a[1]) cout << min({f[1][0][0] + 1, f[1][0][1] + 1, f[1][1][0], f[1][1][1] + 1}) << '\n';
    else cout << min({f[1][0][0] + 1, f[1][0][1] + 2, f[1][1][0] + 1, f[1][1][1]}) << '\n';
}

} // namespace lowspeed_song

:::

难度：青

鲜活指数：4

隐藏／恢复文章

随机文章