solution

求出每个点的sg函数，然后异或起来得到x，如果x为0那么就是先手必败，否则就是先手必胜。

如何求每个点sg函数？对于节点,,(i是j的祖先)。

对于第二问，也就是需要操作一步使得异或和为0。

如果我们把上的一个棋子挪到了上，那么的异或和就会变为，（v位于u的子树中）。也就是说我们要求每个子树u中有多少个v满足。这个我们可以用表示i这个异或值出现的次数，然后在dfs的过程中，在dfs一棵子树之前先记录一下，然后dfs这棵子树之后如果比原来大k的话，说明子树中有k个点满足条件。

复杂度

code

/*
* @Author: wxyww
* @Date: 2020-05-08 20:28:25
* @Last Modified time: 2020-05-08 20:48:24
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int n,sg[N],SG;
void dfs1(int u,int fa) {
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs1(v,u);
        sg[u] = max(sg[u],sg[v] + 1);
    }
    SG ^= sg[u];
}
int p[N];
ll ans = 0;
void dfs2(int u,int fa) {
    p[sg[u]]++;
    int k = p[SG ^ sg[u]];
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs2(v,u);
    }
    ans += p[SG ^ sg[u]] - k;
}

int main() {
    n = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }

    dfs1(1,0);
    if(!SG) {
        puts("NO");return 0;
    }
    dfs2(1,0);
    puts("YES");
    cout<<ans<<endl;
    return 0;
}