相关链接
题目传送门: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; }