相关链接
题目传送门: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; }
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!
Really good info can be found on web blog.
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
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
95249 720874Dead written topic matter, Truly enjoyed reading via . 772802
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
865538 352828Great information many thanks sharing and reaching us your subscriber list. 640866
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
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
733902 864125To know wisdom and instruction, to perceive the words of understanding 146689
752175 415292Nothing better than Bing discovering us a great internet site related to what I was looking for. 96315
440511 594779Some genuinely fascinating info, effectively written and usually user genial . 832071
843245 908925This internet internet site is usually a walk-through its the information you wished about this and didnt know who ought to. Glimpse here, and youll surely discover it. 827757
272207 377108Woh I enjoy your content , saved to favorites ! . 714480
824192 712625HURRAY! cant balladeer. by virtue of himself by what name highly. 671104