AC代碼

https://codeforces.com/contest/1149/submission/183086572

題意：

在Byteland，有兩個(gè)政黨在即將舉行的選舉中爭奪議會(huì)席位：錯(cuò)誤答案黨和超越時(shí)限黨。

由于他們想說服盡可能多的公民投票，他們一直承諾越來越低的稅收。

Byteland有n個(gè)城市，由m條單行道連接。有趣的是，道路網(wǎng)絡(luò)沒有循環(huán)——不可能從任何城市出發(fā)，

沿著多條道路，然后返回該城市。去年，第i個(gè)城市的居民不得不繳納高額稅款。

兩個(gè)政黨 將輪流在各個(gè)城市舉行選舉大會(huì)。如果一個(gè)政黨在v市舉行會(huì)議，

該政黨需要將該市的稅收降至非負(fù)整數(shù)bourles。

然而，同時(shí)，他們可以任意修改每個(gè)城市(可以通過一條道路從v到達(dá))的稅收，?

唯一必須滿足的條件是，每個(gè)城市的稅收必須保持為非負(fù)整數(shù)bourles。

第一個(gè)舉行大會(huì)的政黨是錯(cuò)誤答案黨。

據(jù)預(yù)測，舉行最后一次大會(huì)的政黨將贏得選舉。?

也就是說，所有城市的稅收為0時(shí)，這時(shí)的選手輸

題解：

圖上博弈 + SG函數(shù)

首先求出每個(gè)點(diǎn)的SG函數(shù)值，即SG(u)=mex{SG(v)|v∈son(u)}。

然后求出sum_x=xor {au|SG(u)=x}

那么先手必勝當(dāng)且僅當(dāng)存在sum_x非零。

先手必勝要做的是把所有非零sum_x變成0