僅有距根節(jié)點(diǎn)為奇數(shù)距離的節(jié)點(diǎn)的石子被移走對(duì)答案有貢獻(xiàn)，∵即使偶數(shù)的石子被移走，遲早會(huì)被再移到奇數(shù)，而奇數(shù)被移走后，不一定能夠在移到偶數(shù)(到根了)。

最多移L個(gè)：石子數(shù)模(L+1)，比較顯然，也可以自己跑一跑奇數(shù)層的SG函數(shù)。

#include<cstdio> using namespace std; #define N 10001 int en,v[N],first[N],next[N]; void AddEdge(int U,int V) {v[++en]=V;next[en]=first[U];first[U]=en; } int n,q,m,a[N],ans; void dfs(int U,int d) {if(d&1) ans^=a[U];for(int i=first[U];i;i=next[i])dfs(v[i],d+1); } int main() {int A,B;scanf("%d%d%d",&n,&q,&m);for(int i=2;i<=n;++i){scanf("%d%d",&A,&a[i]);a[i]%=(m+1);AddEdge(A,i);}for(;q;--q){scanf("%d%d",&A,&B);a[A]=B%(m+1);ans=0;dfs(1,0);puts(ans?"Yes":"No");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/autsky-jadek/p/4340480.html

總結(jié)

以上是生活随笔為你收集整理的【博弈论】【SG函数】bzoj1777 [Usaco2010 Hol]rocks 石头木头的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。