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