牛客练习赛63f牛牛的树行棋
牛牛的树行棋
https://ac.nowcoder.com/acm/contest/5531/F
普通的nim游戏：有n堆石子，石子数a1，a2…，每次可以从一堆拿任意个石子，两个人拿，求先手是否赢
nim游戏结论：
1.求所有堆的石子数ai异或和xorsum，如果xorsum！=0，那么先手有必赢策略，否则没有
2.先手第一步应该怎么拿：从a1中拿a1-（a1^xorsum）个石子是a1变为a1^xorsum
nim游戏结论：
1.求所有堆的石子数ai异或和xorsum，如果xorsum！=0，那么先手有必赢策略，否则没有
2.先手第一步应该怎么拿：从a1中拿a1-（a1^xorsum）个石子是a1变为a1^xorsum
本题把每个节点就是一堆石子，对于单链，深度为x就等效于一堆x个石子（sg=x），叶子深度为0
对于有多个子树的father就等效于一堆max子树+1个石子
（因为如图假设father向左子树移动到x=1的位置，那么其实（状态）也等效于它移动到右子树x=1的位置，但左无法等效3移动到右2位置）
那么求出所有sg值的异或和xorsum，如果xorsum！=0，先手有必赢策略，否则没有
怎么求必赢策略中第一步的方法数？
我们用cnt【k】记录从该节点一直向上直到到根节点1，所有sg=k的父辈有多少个
由结论可知，按必赢策略走完第一步到达节点（设为x）的堆的原石子数a1有：
a1^xorsum=sg【x】=>a1=xorsum^xorsum
我们只要累加上所有第一步完后节点的原符合条件的父辈节点数
对于有多个子树的father就等效于一堆max子树+1个石子
（因为如图假设father向左子树移动到x=1的位置，那么其实（状态）也等效于它移动到右子树x=1的位置，但左无法等效3移动到右2位置）
那么求出所有sg值的异或和xorsum，如果xorsum！=0，先手有必赢策略，否则没有
怎么求必赢策略中第一步的方法数？
我们用cnt【k】记录从该节点一直向上直到到根节点1，所有sg=k的父辈有多少个
由结论可知，按必赢策略走完第一步到达节点（设为x）的堆的原石子数a1有：
a1^xorsum=sg【x】=>a1=xorsum^xorsum
我们只要累加上所有第一步完后节点的原符合条件的父辈节点数
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int> e[N];
int sg[N<<1],n,cnt[N<<1],u,v,sum,xorsum;
void dfs1(int x,int pre){
for(auto i:e[x])
if(i!=pre) {
dfs1(i,x);
sg[x]=max(sg[x],sg[i]+1);
}
xorsum^=sg[x];
}
void dfs2(int x,int pre){
cnt[sg[x]]++;
sum+=cnt[sg[x]^xorsum];
for(auto i:e[x])
if(i!=pre) dfs2(i,x);
cnt[sg[x]]--;
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
cin>>u>>v;
e[u].push_back(v), e[v].push_back(u);
}
dfs1(1,-1);
if(xorsum){
dfs2(1,-1);
cout<<"YES"<<endl<<sum<<endl;
}else cout<<"NO"<<endl;
return 0;
}
