牛牛的树行棋

NC204126. 牛牛的树行棋

描述

牛牛和牛妹是一对好朋友，这天他们俩决定在树上玩一个游戏。

游戏的名字是“树行棋”，规则如下：

给定一个含有n个节点分别从1到n编号且以节点1为根的树，一开始每个节点各有1个棋子。

牛牛和牛妹轮流进行操作，且牛牛先手移动。

每次操作可以选择将任意一个棋子移动到其子树中的任意一个节点，但是每次移动必须保证棋子的位置发生变化（不能拿起再放回原处）。

直到无法进行操作，轮到不能操作的一方即为败者。

现在假设双方都采用最优策略，请问牛牛能否赢。
如果牛牛（先手）能够赢，请问牛牛第一步有多少种不同的必胜策略。

我们认为两个策略是不同的，当且仅当这两个策略一开始选择的棋子不同，或者移动的路径不同。

输入描述

第一行输入一个，表示树含有n个点。
接下来n-1行，每行输入一个x，y，()表示x与y相连。

输出描述

对于每组数据，如果牛牛（先手）能赢则输出‘YES’，否则输出‘NO’。
如果能赢，请在第二行跟着输出一个正整数ans，表示第一步的必胜策略数目。

示例1

输入:

3
1 2
1 3

输出:

YES
2

说明:

因为2,3两个节点为叶节点，题目要求每次操作棋子的位置必须产生变化，所以2,3两节点的棋子是无法移动的。

只能操作节点1上的棋子，可以选择将其移动到2或者移动到3，所以共2种必胜决策。

示例2

输入:

输出:

NO

说明:

一上来牛牛有6种移动方案：

1、将1号节点上的棋子移动到2

此时2号节点有两个棋子，3号节点4号节点各有1个棋子，且4号节点的棋子无法移动。

后手只要选择3号节点的棋子将其移动到4号节点，接下来后手完全模仿先手的操作就可以胜利。

...（剩下5种方案由于类似的原因都是后手取得胜利）

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 851ms, 内存消耗: 62316K, 提交时间: 2020-05-12 11:48:47

#include<bits/stdc++.h>
using namespace std;


const int N=1e6+100;

vector<int>G[N];

int cnt[N],sg[N];


int tmp=0,ans=0;
 
void dfs1(int x,int fa)
{ 
	for(int v:G[x])
	{
		if(v==fa) continue;
		dfs1(v,x);
		sg[x]=max(sg[x],sg[v]+1);
	}
	tmp^=sg[x];
}
void dfs2(int x,int fa)
{
	ans-=cnt[tmp^sg[x]];
	cnt[sg[x]]++;
	for(int v:G[x])
	{
		if(v==fa)continue;
		dfs2(v,x);
	}
	ans+=cnt[tmp^sg[x]];
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs1(1,0);
	if(tmp==0) puts("NO");
	else
	{
		puts("YES");
		dfs2(1,0);
		cout<<ans<<endl;
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 718ms, 内存消耗: 53988K, 提交时间: 2020-05-11 01:02:46

#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;
}