题意简化一下其实就是树上移子问题。 分析：在询问前求出每个点的SG函数，xor，然后改变值以后再来一遍，得到的就是全局的sg值，然后判断输出就可以了。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m,t,l; const int N=5e5+5; int a[N]; int head[N],go[N],next[N]; int sg[N],st[N]; int tot; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } inline void dfs(int x,int d) { st[x]=d; int i=head[x]; while (i) { dfs(go[i],d^1); i=next[i]; } } int getsg(int x) { return st[x]==0?0:a[x]%(l+1); } int main() { while (scanf("%d%d%d",&n,&t,&l)==3) { tot=0; memset(head,0,sizeof(head)); fo(i,2,n) { int fa; scanf("%d%d",&fa,&a[i]); add(fa,i); } dfs(1,0); int id,maxn,ans=0; scanf("%d%d",&id,&maxn); a[id]=maxn; fo(i,2,n)ans^=getsg(i); printf("%s\n",ans?"Yes":"No"); fo(i,1,t-1) { scanf("%d%d",&id,&maxn); ans^=getsg(id); a[id]=maxn; ans^=getsg(id); printf("%s\n",ans?"Yes":"No"); } } return 0; }