非常好题目。
发现每个点颜色被反转的次数是固定的,为其深度(根结点深度为 \(0\))。于是可以看作是,一放棋子就得到分数。
那么先手取偶数层和后手取奇数层都会使先手得分,所以双方的目标都是尽可能多取偶数层的结点。
考虑若一开始有偶数层的叶子,那么当前的先手肯定会取它(不取白不取)。可以先维护这种情况。
那么取完偶数层叶子后就只剩下奇数层了。考虑把树分成一个个极大的“坨”,使得每个“坨”都会使得先后手交换,且取这一坨的人不会得分(对方得分)。
显然双方都会取当前能取的最小的坨。取完一坨可能会产生新的坨,把这一坨的价值并到父亲的父亲即可。优先队列维护一下就行了。
注意最后还剩下根结点。
code
// Problem: F - Subtree Reversi
// Contest: AtCoder - AtCoder Regular Contest 164
// URL: https://atcoder.jp/contests/arc164/tasks/arc164_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, p[maxn], ind[maxn], ans, f[maxn];
bool fl = 1;
vector<int> G[maxn];
struct node {
int u, d;
node(int a = 0, int b = 0) : u(a), d(b) {}
};
inline bool operator < (const node &a, const node &b) {
return a.d > b.d;
}
priority_queue<node> pq;
void dfs(int u, int d) {
for (int v : G[u]) {
dfs(v, d ^ 1);
}
if (ind[u] == 0) {
if (d) {
pq.emplace(u, 1);
} else {
ans += fl;
fl ^= 1;
--ind[p[u]];
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 2; i <= n; ++i) {
scanf("%d", &p[i]);
G[p[i]].pb(i);
++ind[p[i]];
}
dfs(1, 0);
while (pq.size()) {
int u = pq.top().u, d = pq.top().d;
pq.pop();
if (p[u] != 1 && !(--ind[p[u]])) {
int v = p[p[u]];
f[v] += d + 1;
if (!(--ind[v])) {
pq.emplace(v, f[v] + 1);
}
} else {
if (!fl) {
ans += d;
}
fl ^= 1;
}
}
ans += fl;
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Subtree Reversiatcoder regular contest subtree atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest builder disconnected atcoder regular contest