非常好题目。
发现每个点颜色被反转的次数是固定的,为其深度(根结点深度为 \(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;
}