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

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

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

可以发现树上的节点

i

，可能最后结果为

0

或

1

，可能操作了也可能没操作，所以有

2\times2=4

种情况。

定义

dp

数组，表示以

i

为根的子树除了点

i

都为

0

的最小操作数，又有上述的

4

种情况：

$dp_{i,0,0}$ ，表示节点 $i$ ，最后结果为 $0$ ，并且没在 $i$ 进行过操作。
$dp_{i,0,1}$ ，表示节点 $i$ ，最后结果为 $0$ ，并且在 $i$ 进行过操作。
$dp_{i,1,0}$ ，表示节点 $i$ ，最后结果为 $1$ ，并且没在 $i$ 进行过操作。
$dp_{i,1,1}$ ，表示节点 $i$ ，最后结果为 $1$ ，并且在 $i$ 进行过操作。

然后我们考虑初始化：

设当点

i

初始状态为

a_i

。（

\oplus

为异或）。

$dp_{i,a_i,0} = 0$ 。表示点 $i$ 不操作，所以点 $i$ 没有变化。
$dp_{i,a_i\oplus1,1} = 1$ 。表示点 $i$ 操作，所以点 $i$ 变化了。
$dp_{i,0,1} = \infty$ 。此操作不可行。
$dp_{i,1,0} = \infty$ 。此操作不可行。

之后考虑转移。
设

j

为

i

的子节点。

可以分为两种情况：

$j$ $j$ 操作过，则点 $i$ $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}$ 。
$j$ $j$ 没操作过，则点 $i$ $i$ 状态没被改变。
- $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})

。

code

CPP

#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;
}

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

文章操作

相关推荐

评论

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