专栏文章
题解：P8127 [BalticOI 2021] The Xana coup (Day2)
P8127题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @min8iplc
- 此快照首次捕获于
- 2025/12/01 22:18 3 个月前
- 此快照最后确认于
- 2025/12/01 22:18 3 个月前
题目概述
给你一颗树并且每个点上面有点权，你可以进行一次操作：选择一个点将他自己和与他距离为 的点的点权全部异或 。
求最少多少次操作使得每个点的点权都是 。
分析
遇到这种题目，一般都是先考虑贪心或者基本算法。
我们考虑从下往上依次使其子树变成 ，我们发现这是可以的，但是却不好判断无解，而且存在非最优解的情况。
所以我们再考虑 。
这类题目一般都是每个点最多改变 次，为什么呢？我要是改变了两次不就相当于没有改变吗。
注意到我们如果从下往上的话，我们的改变实际上只是跟自己的儿子是否变化有关。
考虑维护这样一个 。
设 表示以 为子树，当前 是否改变， 的权值是什么并且使得整个子树除了它都是 的最小操作次数。
转移一一考虑即可（以下记 表示 且 为 的儿子）。
第一种情况：，那么我可以一开始是 但是被我的儿子改变（也就是 ），或者说我一开始是 没有被我的儿子改变（也就是 ）。
第二种情况：，那么我可以一开始是 但是被我的儿子改变（也就是 ），或者说我一开始是 没有被我的儿子改变（也就是 ）。
第三种情况：，那么我可以一开始是 但是我改变之后就变成了 ，又被我的儿子改变回来了（也就是 ）,或者说我一开始是 然后是我自己改变的（也就是 ）。
第四种情况：，那么我可以一开始是 但是我改变之后就变成了 ，我的儿子没有改变我（也就是 ），或者说我一开始是 然后改变之后变成了 ，我的儿子改变了我（也就是 ）。
直接做就行了。
代码
时间复杂度 。
CPP#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;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...