牛客练习赛63 F.牛牛的树行棋

题目大意：
给定一棵树，每个结点上都有一个棋子，牛牛和牛妹两个人每次选择任意一个结点的棋子，将棋子移动到该节点子树下的节点位置。(不可以不移动)牛牛先手，牛妹后手。
现在假设双方都采用最优策略，请问牛牛能否赢。
如果牛牛（先手）能够赢，请问牛牛第一步有多少种不同的必胜策略。
我们认为两个策略是不同的，当且仅当这两个策略一开始选择的棋子不同，或者移动的路径不同。

参考：Lskkkno1 大佬题解 (由于写的急,万分抱歉

https://blog.nowcoder.net/n/6650ed32a8d64f649dd0b370eb22edaa

分析:
前提知识：
SG 函数定义与结论:(粗略解释)
任何一个公平组合游戏都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边.
g(x)表示x局面的SG值, g(x)=mex { g(y) | y是x的后继 }表示x局面内的子局面SG值集合中最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{1,3,5}=0、mex{}=0.
当前SG值为0,先手必输，否则后手必输.
游戏的和的SG函数值是它的所有子游戏的SG函数值的异或.-------因为每个棋子的移动是独立的，那么游戏的SG值等于所有棋子的SG值的异或和.

这道题套用SG函数.
考虑决策叶子节点的棋子,叶子节点的棋子无法移动，所以SG函数为0.
一个结点的子节点只有叶子节点，那么该节点的的SG值为1.
一个结点的所有子节点的中最大SG值为1，那么该子节点的后继节点肯定有0的，那么当前节点的SG值为2.
...
可以推导出，一个结点的SG值等于所有子节点的最大SG值加一.

我们先判断先手是否能必胜，直接计算所有节点的SG值的异或和是否为零.
若先手必胜，考虑计算必胜决策方案个数.
先手必赢的决策： 游戏的SG值为 值不为0，先手要把SG值变为0，那么对于结点x，SG值为 ,我们只需要将该节点的棋子移动到SG值为 的子节点即可。
那么我们可以dfs处理出所有节点的SG值。
因为每个结点只能移动到该子树中的结点，可以用树上差分进行计算方案。

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

typedef long long ll;
const int maxn=5e5+10;

vector<int> g[maxn];
int cnt[maxn<<2];
int mx[maxn];
ll ans;
ll res;

void dfs1( int x,int f )
{
    mx[x]=0;
    for( auto v:g[x] )
    {
        if( v==f ) continue;
        dfs1(v,x);
        mx[x]=max(mx[x],mx[v]+1);
    }
    res^=mx[x];
}

void dfs2( int x,int f )
{
    if( mx[x]>(mx[x]^res) ) ans-=cnt[mx[x]^res];
    cnt[mx[x]]++;
    for( auto v:g[x] )
    {
        if( v==f ) continue;
        dfs2(v,x);
    }
    if( mx[x]>(mx[x]^res) ) ans+=cnt[mx[x]^res];
}

int main()
{
    int n;
    cin>>n;

    for( int i=1;i<n;i++ )
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u); 
    }
    dfs1(1,0);
    dfs2(1,0);
    puts( res ? "YES" : "NO" );
    if( res ) cout<<ans<<endl;
}