F、牛牛的树行棋

博弈论sg函数与dfs。
前导知识sg函数：
SG函数：

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于任意状态 x ， 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。 这样 集合S 的终态必然是空集，所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时。
结论：当一个局面sg值为0时必败，否则对方必败。

sg定理：
那么整局游戏的sg值等于每个子游戏的sg值异或。

那么很显然，叶子节点sg值为0，因为不存在下一个状态。
而其余节点，就是全部子节点的sg值最大在加一。

如果我们求解到树上全部节点的sg异或的值（记为ans）为0说明先手必败。
否则，求解方案数。那么因为状态只能在自己和子节点之间转移。那么我们就要去寻找 sg[u] XOR sg[v] == ans的节点对数。v是u的子节点
假设我们求解的是x节点那么再用 k = ans XOR sg[x]，再另外开一个计数器数组，记录当前根节点下的全部子节点出现的sg值次数
每次把sum += cnt[k]即可。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 5e5 + 7; //大约19个1
vector<int> e[N];
int sg[N], cnt[1 << 20];
int sum, ans;

void dfs1(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa)    continue;
        dfs1(v, u);
        sg[u] = max(sg[u], sg[v] + 1);
    }
    ans ^= sg[u];
}

void dfs2(int u, int fa) {
    ++cnt[sg[u]]; //入栈+1
    int k = ans ^ sg[u];
    sum += cnt[k];
    for (auto v : e[u]) {
        if (v == fa)    continue;
        dfs2(v, u);
    }
    --cnt[sg[u]];
}

int main() {
    int n = read();
    while (--n) {
        int u = read(), v = read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 0);
    if (ans) {
        dfs2(1, 0);
        printf("YES\n%d\n", sum);
    }
    else
        puts("NO");
    return 0;
}