题解：P8127 [BalticOI 2021] The Xana coup (Day2)

· · 题解

题目概述

给你一颗树并且每个点上面有点权，你可以进行一次操作：选择一个点将他自己和与他距离为 1 的点的点权全部异或 1。

求最少多少次操作使得每个点的点权都是 0。

分析

遇到这种题目，一般都是先考虑贪心或者基本算法。

我们考虑从下往上依次使其子树变成 0，我们发现这是可以的，但是却不好判断无解，而且存在非最优解的情况。

所以我们再考虑 dp。

这类题目一般都是每个点最多改变 1 次，为什么呢？我要是改变了两次不就相当于没有改变吗。

注意到我们如果从下往上的话，我们的改变实际上只是跟自己的儿子是否变化有关。

考虑维护这样一个 dp。

设 f_{i,0/1,0/1} 表示以 i 为子树，当前 i 是否改变，i 的权值是什么并且使得整个子树除了它都是 0 的最小操作次数。

转移一一考虑即可（以下记 (a,b,c) 表示 f_{a,b,c} 且 j 为 i 的儿子）。

第一种情况：(i,0,0)，那么我可以一开始是 1 但是被我的儿子改变（也就是 (j,1,0)），或者说我一开始是 0 没有被我的儿子改变（也就是 (j,0,0)）。

第二种情况：(i,0,1)，那么我可以一开始是 0 但是被我的儿子改变（也就是 (j,1,0)），或者说我一开始是 1 没有被我的儿子改变（也就是 (j,0,0)）。

第三种情况：(i,1,0)，那么我可以一开始是 0 但是我改变之后就变成了 1，又被我的儿子改变回来了（也就是 (j,1,1)）,或者说我一开始是 1 然后是我自己改变的（也就是 (j,0,1)）。

第四种情况：(i,1,1)，那么我可以一开始是 0 但是我改变之后就变成了 1，我的儿子没有改变我（也就是 (j,0,1)），或者说我一开始是 1 然后改变之后变成了 0，我的儿子改变了我（也就是 (j,1,1)）。

直接做就行了。

代码

时间复杂度 \mathcal{O}(n)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 100005
using namespace std;
int f[N][2][2],a[N],n;
vector<int> g[N];
void dfs(int cur,int fa) {
    for (auto i : g[cur])
        if (i != fa) {
            dfs(i,cur);
            int _00 = f[i][0][0],_01 = f[i][0][1],_10 = f[i][1][0],_11 = f[i][1][1];
            int lst00 = f[cur][0][0],lst01 = f[cur][0][1],lst10 = f[cur][1][0],lst11 = f[cur][1][1];
            f[cur][0][0] = min(lst00 + _00,lst01 + _10);
            f[cur][0][1] = min(lst00 + _10,lst01 + _00);
            f[cur][1][0] = min(lst10 + _01,lst11 + _11);
            f[cur][1][1] = min(lst10 + _11,lst11 + _01);
        }
}
signed main(){
    cin >> n;
    for (int i = 1;i <= n;i ++) 
        for (int j = 0;j < 2;j ++)
            for (int k = 0;k < 2;k ++) f[i][j][k] = 1e13;
    for (int i = 1;i < n;i ++) {
        int u,v;
        scanf("%lld%lld",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]),f[i][0][a[i]] = 0,f[i][1][a[i] ^ 1] = 1;
    dfs(1,0);
    int ans = min(f[1][1][0],f[1][0][0]);
    if (ans <= n) cout << ans;
    else puts("impossible");
    return 0;
}