洛谷 P11018 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-08-20 21:43:06

发布于：天津

5阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有一棵树，树上的节点只会为黑色 ( $1$ ) 或者白色 $(0)$
允许：
有两个操作

操作1：将节点 $u$ 到根节点路径上的所有点颜色反转
操作2：将以 $u$ 为根的子树中所有节点（包括 $u$ ）的颜色全部反转

要求操作过后最终使得所有点为黑色时的最小操作次数

1.3 题目数据范围与猜测

$1 \le n \le 2\times 10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一棵树，树上每个节点有颜色
求将树通过题目给出操作全部染为黑色的最小操作次数

2 题目破题推导

2.1 第一步：观察影响

发现当一个节点使用操作2时，只会对底下所有子节点产生影响
但是当一个节点使用操作1时，会对上面的所有点产生影响，其中包括了直接父节点

2.2 第二步：奇偶性分析

我们先只考虑一个节点重复使用操作1对于其父节点的影响：
若使用操作1次数为奇数（异或和为 $1$ ），则其父节点将会被翻转，否则将不会
接下来就要就着简单思路讨论了

3 模型匹配（代码和模型匹配中的描述略有不同）

1.dp状态的设定
    f[i][0/1][0/1]:以i为根节点的子树全为0/1且操作1的次数为偶数/奇数的最小操作次数
2.初始化
    令 u 节点颜色为 color[u]
    对叶子结点状态初始化:
        f[u][color[u]][0] = 0 不用操作1且最终颜色不变，代表一次都不用操作
        f[u][!color[u]][0] = 1 不用操作1但是最终整体颜色反转，代表使用了一次操作2
        f[u][!color[u]][1] = 1 使用了1（奇数）次操作1且最终整体颜色反转
                               说明使用且仅使用了1次操作1用于反转叶子节点颜色
        f[u][color[u]][1] = 2 使用了1（奇数）次操作1并且当前节点颜色并未被反转
                              说明又使用了一次操作2抵消
3.转移前的预处理
    对于u,一共有cnt[u]个子节点,子节点为v[i],当前子节点为v
    for (int i = 1;i <= cnt[u];i++){
        g[0/1][0/1]:前面处理过的i-1个孩子分别对应的子树达到子树全为0/1
                    且前i-1棵子树使用操作1的总次数为偶数/奇数的操作总数
        然后再来一个滚动数组t(省空间)
    }
    首先我们的预处理一定要保证t,g和f都处理的是所有孩子节点颜色相同
    t[0][0] = min(g[0][0] + f[v][0][0], g[0][1] + f[v][0][1])
    最终操作1使用了偶数次，偶数=偶数+偶数（0+0），偶数=奇数+奇数（1+1）
    t[0][1] = min(g[0][1] + f[v][0][0], g[0][0] + f[v][0][1])
    最终操作1使用了奇数次，奇数=奇数+偶数（1+0），奇数=偶数+奇数（0+1）

    子树全为1的代码同理，不再介绍
    t[1][0] = min(g[1][0] + f[v][1][0], g[1][1] + f[v][1][1])
    t[1][1] = min(g[1][1] + f[v][1][0], g[1][0] + f[v][1][1])
4.状态转移
    f[u][color[u]][0] = min(g[color[u]][0], g[color[u]][1] + 1)
    当前节点操作完后希望颜色不变，且孩子操作完后对于当前节点来说操作1进行了偶数次
    那么只有两种可能：
    要么孩子和当前节点颜色一样且操作1执行了偶数次
    这时满足奇偶性，偶数+0=偶数，满足转移时的定义
    要么孩子和当前节点颜色一样但是进行了奇数次操作1，再花1次对于u的操作1用于单独反转
    这时满足奇偶性，奇数+1=偶数，满足转移时的定义
    f[u][!color[u]][0] = min(g[color[u]][0] + 1, g[color[u]][1] + 2)
    当前节点操作完后希望颜色改变，且孩子操作完后对于当前节点来说操作1进行了偶数次
    那么只有两种可能：
    要么孩子和当前节点颜色一样且操作1执行了偶数次，这时需要整体花一次操作2整体反转
    这时满足奇偶性，偶数+0=偶数，满足转移时的定义
    要么孩子和当前节点颜色一样但是进行了奇数次操作1，再花1次对于u的操作1用于单独反转，然后再来一次整体的反转
    这时满足奇偶性，奇数+1=偶数，满足转移时的定义
    f[u][!color[u]][1] = min(g[!color[u]][0] + 1, g[!color[u]][1])
    当前节点操作完后希望颜色改变，且孩子操作完后对于当前节点来说操作1进行了奇数次
    那么只有两种可能：
    要么孩子和当前节点颜色不同且操作1执行了偶数次，这时需要整体花一次操作1单独改变自己的颜色
    这时满足奇偶性，偶数+1=奇数，满足转移时的定义
    要么孩子和当前节点颜色不同但是进行了奇数次操作1，无需任何额外花费，孩子带来的奇数次操作1已经为当前节点改变了颜色
    这时满足奇偶性，奇数=奇数，满足转移时的定义
    f[u][color[u]][1] = min(g[!color[u]][0] + 2, g[!color[u]][1] + 1)
    当前节点操作完后希望颜色不变，且孩子操作完后对于当前节点来说操作1进行了奇数次
    那么只有两种可能：
    要么孩子和当前节点颜色不同且操作1执行了偶数次，这时需要先花一次操作1反转当前节点的颜色，再进行一次操作2整体反转
    这时满足奇偶性，偶数+1=奇数，满足转移时的定义
    要么孩子和当前节点颜色不同但是进行了奇数次操作1，这奇数次的操作1已经帮助当前节点反转了颜色，再进行一次操作2整体反转
    这时满足奇偶性，奇数+0=奇数，满足转移时的定义

4 最终代码（禁止抄袭，仅用于参考）

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

const int MAXN = 200005;
const int INF = 0x3f3f3f3f;

int n;
int color[MAXN];
int parent[MAXN];
int dp[MAXN][2][2];
int cur[MAXN][2][2];
int tmp[MAXN][2][2];
vector<int> adj[MAXN];

void build_parent(int u) {
    for (int v : adj[u]) {
        if (v == parent[u]) continue;
        parent[v] = u;
        build_parent(v);
    }
}

void dfs(int u) {
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            tmp[u][i][j] = cur[u][i][j] = INF;
        }
    }
    tmp[u][0][0] = 0;
    tmp[u][1][0] = 0;
    for (int v : adj[u]) {
        if (v == parent[u]) continue;
        dfs(v);
    }
    if (adj[u].size() == 1 && adj[u][0] == parent[u]) {
        dp[u][color[u]][0] = 0;
        dp[u][color[u] ^ 1][0] = 1;
        dp[u][color[u] ^ 1][1] = 1;
        return;
    }
    for (int v : adj[u]) {
        if (v == parent[u]) continue;
        cur[u][0][0] = min(tmp[u][0][0] + dp[v][0][0], tmp[u][0][1] + dp[v][0][1]);
        cur[u][0][1] = min(tmp[u][0][1] + dp[v][0][0], tmp[u][0][0] + dp[v][0][1]);
        cur[u][1][0] = min(tmp[u][1][0] + dp[v][1][0], tmp[u][1][1] + dp[v][1][1]);
        cur[u][1][1] = min(tmp[u][1][1] + dp[v][1][0], tmp[u][1][0] + dp[v][1][1]);
        tmp[u][0][0] = cur[u][0][0];
        tmp[u][0][1] = cur[u][0][1];
        tmp[u][1][0] = cur[u][1][0];
        tmp[u][1][1] = cur[u][1][1];
    }
    int c = color[u];
    dp[u][c][0] = min(cur[u][c][0], cur[u][c][1] + 1);
    dp[u][c][1] = min(cur[u][c ^ 1][1] + 1, cur[u][c ^ 1][0] + 2);
    dp[u][c ^ 1][0] = min(cur[u][c][0] + 1, cur[u][c][1] + 2);
    dp[u][c ^ 1][1] = min(cur[u][c ^ 1][1], cur[u][c ^ 1][0] + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> color[i];
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    memset(dp, 0x3f, sizeof(dp));
    build_parent(1);
    dfs(1);
    cout << min(dp[1][1][0], dp[1][1][1]) << '\n';

    return 0;
}
// 老师帮我调了好多