牛客-牛の木の碁

タイトルの説明
牛の木碁
解法:SG関数+DFS(C++)
詳しくはLskkkkno 1の解と段三園の小迷弟の解を参考に
まずSG関数に関する二つの結論を紹介する.

現在の局面のSG値は0で、先手は必ず負けて、さもなくば先手は必ず

に勝つ

1 1つのゲームが複数の独立ゲームからなる場合、現在の局面のSG値は複数の独立ゲームSG値の異或値

である.
では、この問題にとって、各駒は実は独立している.つまり、現在の局面の複数の独立ゲームは各駒であり、現在の局面のSG値は各駒のSG値の異和である.
では、1枚の駒のSG値はどのように求めますか?
1枚の駒が葉ノード(後続状態が空セット)にある場合、そのSG値は0である
1枚の駒の後継ノードが葉ノードのみである場合,そのSG値は1である.
1枚の駒の後継ノードSGの値が最大1であれば(必ず0もある)、そのSGの値は2である
1枚の駒の後継ノードSGの値が最大2であれば(1,0もあるに違いない)、そのSGの値は3である
⋯ ⋯\cdots\cdots ⋯⋯
すなわち、リーフノードを除いて、各ノードのSG値は、m a x(サブツリーのS G値)+1 max(サブツリーのSG値)+1 max(サブツリーのSG値)+1に等しい
以上の結論から,すべてのSG値の異和とx x o r xor xorを求め,x x o r!=0 xxor != 0 xxor!=0、先手は必ず勝つ策略があって、さもなくば必ず負けます
では、必勝を知ったらどうやって方法数を解くのでしょうか.
SG値が0の局面は必ず負けるので、つまり、私たちは初めて移動した後に局面のSG値を必ず0に等しくする必要がある.
現在移動する駒をi i iとし,そのSG値をS G i SG_とする.i SGi、かつ移動前局面のSG値をx x o r xor xor、移動後総SG値を0とするには、この駒はSG値がS G iに等しいまで移動する必要があるioplus xxor SGi谯xxorの位置
そこで,カウント配列c n t[.]を通過する.cnt[...] cnt[...],現在のルートノードの下にある全てのサブノードに出現するSG値の回数を記録し、c n t[S G i攝x x x o r]cnt[SG_ioplus xor]cnt[SGi攝xor]を求めることが望ましい結果である
もちろん、cnt[sg[x]]++; cnt[sg[x]]--;は、DFSがリーフノードに到達して遡及したときに通る道が計算済みであることを保証するため、減らさなければ計算を繰り返す

#include 

using namespace std;

const int N = 5e5+10;
vector<int> e[N];
int n, u, v, sum, xxor, sg[N<<1], cnt[N<<1];

void dfs1(int x, int pre){
    //         sg  ，        
    for(auto i: e[x])
    {
        if(i!=pre)
        {
            dfs1(i, x);
            sg[x] = max(sg[x], sg[i]+1);
        }
    }
    xxor ^= sg[x];
}

void dfs2(int x, int pre){
    //               
    cnt[sg[x]]++;
    sum += cnt[sg[x]^xxor];
    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(xxor)
    {
        dfs2(1, -1);
        cout << "YES" << endl;
        cout << sum << endl;
    }
    else cout << "NO" << endl;
    return 0;
}