Codeforces 812E Sagheer and Apple Tree

时间:2021-05-14 23:57:15

大致题意:

给你一颗树,这个树有下列特征:每个节点上有若干个苹果,且从根节点到任意叶子节点的路径长度奇偶性相同。

甲和乙玩(闲)游(得)戏(慌)。

游戏过程中,甲乙轮流将任意一个节点的若干个苹果移向它的一个叶子节点,若没有叶子节点,那么这些苹果就消失了(被吃掉了)。

若一个玩家没法操作,那么算他输。

游戏由甲开始,而乙可以先选择将两个节点上的苹果数交换一下。问乙有多少种交换方式,使得最后乙获胜。

Nim游戏:

如果懂Nim游戏的话,就不要看了\(^o^)/~你肯定会这道题了。

懂Nim游戏的定义,不懂证明的孩子们,跳过6行往下看。

这6行是写给萌新的Codeforces 812E  Sagheer and Apple Tree

让懒惰的我摘录一段百度百科的话Codeforces 812E  Sagheer and Apple Tree

Codeforces 812E  Sagheer and Apple Tree

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

Codeforces 812E  Sagheer and Apple Tree

简单来说,只要把每一堆的石子数全部xor起来,最后得到0,则后手有必胜策略,否则先手有必胜策略。

Nim游戏结论证明:

不想看证明,想看本题做法的,跳过13行往下看。

让我来描述一下,假如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知道互相都使用必胜策略的话,他们也就不会喜欢玩这个游戏了。

因为,一开始游戏的局面决定了,谁能赢Codeforces 812E  Sagheer and Apple Tree

let me see——

题目中有一个非常好的条件Codeforces 812E  Sagheer and Apple Tree

于是本题就从非常难变成了非常简单。

设,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。

代码:

 #include <cstdio>
#include <iostream>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
int read(){
char c=getchar();int d=,f=;
for(;c<''||c>'';c=getchar())if(c=='-')f=-;
for(;c>=''&&c<='';d=d*+c-,c=getchar());
return d*f;
}
const int N=,M=;
int n,cnt,t[M],d[N],a[N],head[N],to[N],nxt[N];
void addedge(int x,int y){
++cnt;to[cnt]=y;nxt[cnt]=head[x];head[x]=cnt;
}
void dfs(int x){
for(int i=head[x];i;i=nxt[i]){
dfs(to[i]);
d[x]=d[to[i]]^;
}
}
int main()
{
n=read();
ref(i,,n)a[i]=read();
ref(i,,n)addedge(read(),i);
dfs();
int tmp=,tot=;
long long ans=;
ref(i,,n)if(!d[i])tmp^=a[i];
ref(i,,n)if(d[i])t[a[i]]++,tot++;
if(tmp==)ans=1LL*tot*(tot-)/+1LL*(n-tot)*(n-tot-)/;
ref(i,,n)if(!d[i])ans+=t[tmp^a[i]];
printf("%lld\n",ans);
}