【Codeforces 812E】Sagheer and Apple Tree

相关链接

题目传送门:http://codeforces.com/contest/812/problem/E
官方题解:http://codeforces.com/blog/entry/52318

解题报告

我们发现,如果操作同叶子结点的深度奇偶性不同的结点
那么对手总可以操作刚刚你操作的那些苹果

所以结果只与深度同叶子结点奇偶性相同的点有关
更进一步观察发现,实质上就是这些点组成的$NIM$游戏
于是乘一乘、加一加就好了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 10000009;

int n, prt, tot, dep[N], v[N], in[N];
int head[N], nxt[N], to[N], cnt[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1; in[v]++; in[u]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

void DFS(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		dep[to[i]] = dep[w] + 1;
		DFS(to[i]);
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i <= n; i++) {
		v[i] = read();
	}
	for (int i = 2; i <= n; i++) {
		AddEdge(read(), i);
	}
	DFS(1);
	for (int i = 2; i <= n; ++i) {
		if (in[i] == 1) {
			prt = (dep[i] & 1);
			break;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			ans ^= v[i];
		}
	}
	LL vout = 0;
	tot = n;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			cnt[v[i]]++;
			--tot;
		}
	}
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) != prt) {
			int tt = ans ^ v[i];
			if (tt < M) {
				vout += cnt[tt];
			}
		}
	}
	if (!ans) {
		vout += tot * (tot - 1ll) / 2;
		vout += (n - tot) * (n - tot - 1ll) / 2;
	}
	cout<<vout<<endl;
	return 0;
}

15 thoughts to “【Codeforces 812E】Sagheer and Apple Tree”

  1. Hey there! I’m at work surfing around your blog from my new apple iphone! Just wanted to say I love reading through your blog and look forward to all your posts! Keep up the excellent work!

  2. 880300 90166The next time Someone said a weblog, I hope that it doesnt disappoint me just as a lot as this. Come on, man, I know it was my choice to read, but When i thought youd have some thing intriguing to say. All I hear is really a handful of whining about something you can fix inside the event you werent too busy looking for attention. 322247

  3. 398830 875755Dude.. My group is not considerably into seeking at, but somehow I acquired to read several articles on your weblog. Its great how interesting it is for me to go to you fairly often. 123109

  4. 493175 823019This is a excellent subject to talk about. Normally when I uncover stuff like this I stumble it. This article probably wont do well with that crowd. I will probably be confident to submit something else though. 822281

  5. 538345 35385This really is a right blog for would like to uncover out about this subject. You realize a good deal its almost challenging to argue along (not that I personally would wantHaHa). You actually put the latest spin with a subject thats been discussed for a long time. Fantastic stuff, just fantastic! 828954

  6. 661093 303021It is practically impossible to uncover knowledgeable men and women during this subject, even so you sound like do you know what youre discussing! Thanks 207504

Leave a Reply

Your email address will not be published. Required fields are marked *