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

zengzidi · 2025-11-08 18:49:59 · 题解

由于题目给的是一棵树，很明显要用树形 DP。

根据 DP 的步骤。我们先定义状态。

可以发现树上的节点 i，可能最后结果为 0 或 1，可能操作了也可能没操作，所以有 2\times2=4 种情况。

定义 dp 数组，表示以 i 为根的子树除了点 i 都为 0 的最小操作数，又有上述的 4 种情况：

然后我们考虑初始化：

设当点 i 初始状态为 a_i。（\oplus 为异或）。

之后考虑转移。\ 设 j 为 i 的子节点。

可以分为两种情况：

• - $dp_{i,0,0}=dp_{i,1,0}+dp_{j,0,1}$。 - $dp_{i,1,0}=dp_{i,0,0}+dp_{j,0,1}$。 - $dp_{i,0,1}=dp_{i,1,1}+dp_{j,1,1}$。 - $dp_{i,1,1}=dp_{i,0,1}+dp_{j,1,1}$。
• - $dp_{i,0,0}=dp_{i,0,0}+dp_{j,0,0}$。 - $dp_{i,1,0}=dp_{i,1,0}+dp_{j,0,0}$。 - $dp_{i,0,1}=dp_{i,0,1}+dp_{j,1,0}$。 - $dp_{i,1,1}=dp_{i,1,1}+dp_{j,1,0}$。

这两种情况取较小值。

由于转移中需要要用到本身，为了防止出现一种状态使用已转移的状态来转移，所以在每次转移前先用 4 个变量把每种状态记录下来，用记录下来的值转移。

最后是输出答案，设我们已 root 为树根开始计算，则答案为 \min(dp_{root,0,1},dp_{root,0,0})。

:::success[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5,inf=1e15;
int a[maxn],b[maxn],c[maxn][2][2],n,m,d[maxn];
vector<int>aa[maxn];
void dfs(int x,int fa)
{
    c[x][a[x]][0]=0;
    c[x][a[x]^1][1]=1;
    c[x][a[x]][1]=c[x][a[x]^1][0]=inf;
    for(int i=0;i<aa[x].size();i++)
    {
        int to=aa[x][i];
        if(to==fa)continue;
        dfs(to,x);
        int c00=c[x][0][0],c01=c[x][0][1],c10=c[x][1][0],c11=c[x][1][1];
        c[x][0][0]=min(c00+c[to][0][0],c10+c[to][0][1]);
        c[x][1][0]=min(c00+c[to][0][1],c10+c[to][0][0]);
        c[x][0][1]=min(c01+c[to][1][0],c11+c[to][1][1]);
        c[x][1][1]=min(c11+c[to][1][0],c01+c[to][1][1]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        aa[x].push_back(y);
        aa[y].push_back(x);
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1,0);
    int z=min(c[1][0][0],c[1][0][1]);
    if(z<inf)cout<<z;
    else cout<<"impossible";
    return 0;
}

:::