Codeforces 812ESagheer and Apple Tree _Codeforces

关山初度尘未洗，策马扬鞭再奋蹄！这篇文章主要讲述Codeforces 812ESagheer and Apple Tree相关的知识，希望能为你提供帮助。
大致题意：
给你一颗树，这个树有下列特征：每个节点上有若干个苹果，且从根节点到任意叶子节点的路径长度奇偶性相同。
甲和乙玩（闲）游（得）戏（慌）。
游戏过程中，甲乙轮流将任意一个节点的若干个苹果移向它的一个叶子节点，若没有叶子节点，那么这些苹果就消失了（被吃掉了）。
若一个玩家没法操作，那么算他输。
游戏由甲开始，而乙可以先选择将两个节点上的苹果数交换一下。问乙有多少种交换方式，使得最后乙获胜。
Nim游戏：
如果懂Nim游戏的话，就不要看了\\(^o^)/~你肯定会这道题了。
懂Nim游戏的定义，不懂证明的孩子们，跳过6行往下看。
这6行是写给萌新的

文章图片

让懒惰的我摘录一段百度百科的话

文章图片
：

文章图片

让我们来看一下美妙绝伦的结论：

文章图片

简单来说，只要把每一堆的石子数全部xor起来，最后得到0，则后手有必胜策略，否则先手有必胜策略。
Nim游戏结论证明：
不想看证明，想看本题做法的，跳过13行往下看。
【Codeforces 812ESagheer and Apple Tree】让我来描述一下，假如xor起来是0的话，后手的必胜策略。
我们先设每一堆石头数全部xor起来，得到的结果是p。
一开始p=0。
假如先手选中一堆石头，这一堆石头数为x，他拿走了一些石头，剩余石头数为y。
那么我们记 t=x^y。
容易知道，t≠0，先手操作之后，p=t≠0。
于是，容易知道，后手一定能找到一堆石头（石头数为a），满足a^t< a，
因为一定能找到一个a，它与t的二进制最高位都为1。（这点都理解不了就放弃OI吧……好吧开个玩笑）
那么，后手将a变为a^t之后，p重新变为0。
于是，先手操作之后，p永远不为0，后手操作之后，p永远都是0。而游戏并不是永无止境的，所以一定是后手赢。
那么，假设一开始p≠0，先手策略是什么呢？
显而易见，就是找一堆石头（石头数为a），满足a^p< a，
先手将a变成a^p，使得p变为0。接着跟后手策略一样做即可。
本题做法：
也许当该游戏的玩家Sagheer and Soliman知道互相都使用必胜策略的话，他们也就不会喜欢玩这个游戏了。
因为，一开始游戏的局面决定了，谁能赢

文章图片
。
let me see——
题目中有一个非常好的条件

文章图片
，
于是本题就从非常难变成了非常简单。
设，d[x]表示x到该子树中某一个叶子节点的路径长度的奇偶性。（0表示偶数，1表示奇数）
假如后手一开始不能交换节点，那么后手策略可以是这样：
假设d值为1的点属于集合1，d值为0的点属于集合0。
①：先手将集合1中的点x的y个苹果往下移到了z，
那么我们知道d[z]=0，则后手可以将z的y个苹果往下移
②假如把集合0中的点列出来，那么这就是一个典型的Nim游戏。
只要这些点上的苹数xor起来的值p=0，后手就能赢。
回到原题：后手一开始有机会交换两个节点。
假设p=0，后手可以交换集合0中的任意两个点，或集合1中的任意两个点。
否则，肯定要将集合0中的一个点与集合1中的一个点交换了。
弄一个桶，枚举ok。
代码：

1 #include < cstdio> 2 #include < iostream> 3 using namespace std; 4 #define ref(i,x,y)for(int i=x; i< =y; ++i) 5 int read(){ 6char c=getchar(); int d=0,f=1; 7for(; c< ‘0‘||c> ‘9‘; c=getchar())if(c==‘-‘)f=-1; 8for(; c> =‘0‘& & c< =‘9‘; d=d*10+c-48,c=getchar()); 9return d*f; 10 } 11 const int N=100001,M=16777216; 12 int n,cnt,t[M],d[N],a[N],head[N],to[N],nxt[N]; 13 void addedge(int x,int y){ 14++cnt; to[cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; 15 } 16 void dfs(int x){ 17for(int i=head[x]; i; i=nxt[i]){ 18dfs(to[i]); 19d[x]=d[to[i]]^1; 20} 21 } 22 int main() 23 { 24n=read(); 25ref(i,1,n)a[i]=read(); 26ref(i,2,n)addedge(read(),i); 27dfs(1); 28int tmp=0,tot=0; 29long long ans=0; 30ref(i,1,n)if(!d[i])tmp^=a[i]; 31ref(i,1,n)if(d[i])t[a[i]]++,tot++; 32if(tmp==0)ans=1LL*tot*(tot-1)/2+1LL*(n-tot)*(n-tot-1)/2; 33ref(i,1,n)if(!d[i])ans+=t[tmp^a[i]]; 34printf("%lld\\n",ans); 35 }