526互联

AtCoder Regular Contest 164 F Subtree Reversi

发布时间 2023-10-26 21:25:30作者: zltzlt

洛谷传送门

AtCoder 传送门

非常好题目。

发现每个点颜色被反转的次数是固定的，为其深度（根结点深度为 \(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;
}