题目链接
题解
知识点:贪心,博弈论。
一个 \(01\) 串中 \(01, 10\) 的个数差只与首尾两个字符相关,若首尾字符相同,则个数差为 \(0\) ,否则为 \(1\) 或 \(-1\) 。因此,树上除了根节点和叶子节点的 \(?\) 是不影响叶子节点权值的(但可能影响策略,导致答案不一样),我们只需要考虑叶子节点和根节点的情况即可。
设 \(cnt_0, cnt_1, cnt_2\) 分别为值为 \(0, 1, ?\) 的叶子节点个数。
如果根节点不是 \(?\) ,那么答案显然为与根节点值相反的叶子节点数,加上 \(\lceil cnt_2 / 2 \rceil\) 。接下来考虑根节点是 \(?\) 的情况。
当 \(cnt_0 \neq cnt_1\) 时,不妨设 \(cnt_0 < cnt_1\) ,先手有如下几种策略:
- 先手第一步确定根节点的值为 \(0\) ,此时答案为 \(cnt_1 + \lfloor cnt_2 / 2 \rfloor\) 。
- 先手第一步确定根节点的值为 \(1\) ,此时答案为 \(cnt_0 + \lfloor cnt_2 / 2 \rfloor\) 。
- 先手第一步确定一个叶子节点为 \(0\) ,那么后手可以确定根节点为 \(1\) ,此时答案为 \(cnt_0 + \lfloor cnt_2 / 2 \rfloor + 1\) 。
- 先手第一步确定一个叶子节点为 \(1\) ,那么后手可以确定根节点为 \(1\) ,此时答案为 \(cnt_0 + \lfloor cnt_2 / 2 \rfloor\) 。
显然第一种策略答案最优。
当 \(cnt_0 = cnt_1\) 时,有如下几种情况:
- 不存在非根节点和叶子节点的 \(?\) ,无论如何答案都为 \(cnt_0 + \lfloor cnt_2 / 2 \rfloor\) 。
- 存在一个非根节点和叶子节点的 \(?\) ,先手可以选择一个非根节点和叶子节点的 \(?\) 随意赋值,后手无论如何赋值,答案都为 \(cnt_0 + \lceil cnt_2 / 2 \rceil\) 。
- 存在多个非根节点和叶子节点的 \(?\) ,如果数量为偶数,则与不存在的情况等价,否则与存在一个的情况等价。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int deg[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) deg[i] = 0;
for (int i = 2;i <= n;i++) {
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
}
string s;
cin >> s;
s = "?" + s;
int cnt[3] = {};
for (int i = 2;i <= n;i++) if (deg[i] == 1) cnt[s[i] == '?' ? 2 : s[i] == '1']++;
if (s[1] != '?') cout << cnt[s[1] == '0'] + (cnt[2] + 1) / 2 << '\n';
else {
if (cnt[0] == cnt[1]) {
int delta = count(s.begin() + 1, s.end(), '?') - cnt[2] - 1;
cout << cnt[0] + (cnt[2] + (delta & 1)) / 2 << '\n';
}
else cout << max(cnt[0], cnt[1]) + cnt[2] / 2 << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
没有回复内容