[Usaco2010 Hol]rocks 石头木头 【博弈、NIM和、SG函数】

【题目链接】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1777
http://ace.delos.com/ioiupload?d=gold&a=nejLCFTaRn6&lang=ch
【Experience】
呃，今天弄了一下那个论文，以及参详了DD——崔牛的神文的一部分。
神文地址：http://hi.baidu.com/yufuwan1/blog/item/4bb477443c425d4a500ffe2d.html
此乃转载地址，好像原地址已经消失不见了。。。
于是论文自然就是WC2009的：《从“k倍动态减法游戏”出发探究一类组合游戏问题》
然后表示，NIM积依然不懂，第一个例子就不懂。。。
幸好这题不用NIM积。。。
【算法分析】
首先我们可以发现，如果是离根距离为偶数的点上面的石头是不可能决定胜负的。
因为，假设一个人把一些石头从偶点移动一次，那么就到达一个奇点，然后另外一个人就能再从这个奇点移同样数目的石头到偶点。直到这些石头到根。
如果按照这个策略做的话，结果不会发现任何改变。
所以偶点的石头与胜负无关。
然后接下来我们来看奇点的石头。
假设我们从这个奇点移了一些石头，那么再偶数点上的石头再次对结果无关。
所以，每个奇点上的石头是独立的。
有了独立这个性质，那么我们就可以利用Sprague-Grundy Theorem
来处理。如果你看了上面崔牛那篇的第二部分，那么就很容易想到了。
因为是独立的游戏，那么SG(X)=SG(a1)^SG(a2)^…^SG(an)。(^即xor)
如果SG(X)=0，那么证明X是先手必败态。
然后每次只能移L这么多个石头，有一种很简单的方法得出每一个奇点的SG函数值。
就是SG=Rocks_Num%(L+1)。
如果你看了DD那篇神文。
就容易知道SG是怎么求出来的了。
就是画一个有向图，每个点代表剩下x个石子时候的局面，然后再连转移的有向边，然后。。。就能发现规律了。
于是根据Sprague-Grundy Theorem，我们可以轻易得到整个局面的SG函数。
然后剩下的问题是关心在它变那些值的时候我们怎么处理。
由于我们实际上就是需要维护整个局面的SG值，于是我们可以围观到这样的式子：
Ans=k ^ Ai
Ans’=k ^ Ai‘
于是Ans’=k ^ Ai ^ Ai ^ Ai’=Ans ^ Ai ^ Ai’
嗯，就这样。
【CODE】
/*
ID:jie22221
TASK:rocks
LANG:C++
*/
#include int N,T,L,ans,fa,i,w,x;
int d[10005],SG[10005];

int main(){
freopen("rocks.in","r",stdin);
freopen("rocks.out","w",stdout);
scanf("%d%d%d",&N,&T,&L);
d[1]=0; SG[1]=ans=0;
for (i=2;i<=N;i++){
scanf("%d%d",&fa,&w);
d[i]=d[fa]+1;
SG[i]=w%(L+1);
if (d[i]%2==1) ans^=SG[i];
}
for (i=1;i<=T;i++){
scanf("%d%d",&x,&w);
if (d[x]%2==1){
w%=(L+1);
ans^=SG[x]^w;
SG[x]=w;
}
if (ans==0) puts("No");
else puts("Yes");
}
}