先放上今日的原題，供大家先稍加思考一下

WYF互相追逐的頭

題目的閱讀量比較大，而且數(shù)據(jù)比較清奇，但是我們可以知道的是每一個頭都在盡力追逐自己喜歡的那個頭，因此和它同方向（也就是不知道往哪移動）必然就是早晚的事情。

所以如果互相追逐的頭之間的追逐關(guān)系形成一個環(huán)的話，WYF的這些頭到最后必然會不知道往哪去，因此只要我們能夠判環(huán)，則此題可以解之。

但是我們在解題的時候要注意一點：輸入的數(shù)據(jù)描述種存在一種可能性，使得兩群頭之間不存在任何追逐的關(guān)系，針對這種情況，解決方案就是將聯(lián)通的節(jié)點之間打上標(biāo)記，然后沒有被標(biāo)記的節(jié)點再次進行判環(huán)，其實只要找到了一個環(huán)就立刻輸出即可，這道題特判，判分很松。

下放代碼，代碼量兩題都很大，但是MAFIJA的部分代碼可以完全抄WYF的頭的。

MAFIJA

簡單聊一下題意和本質(zhì)。狼人和民眾數(shù)量未知，每個人之間互相揭發(fā)，狼人知道誰是什么角色，因此不會揭發(fā)同伙，平民則是在隨機揭發(fā)，他們的揭發(fā)沒有任何價值。

由此可見我們可以忽略平民的揭發(fā)，狼人揭發(fā)的一定是平民，但是我們現(xiàn)在并不知道狼人和平民誰是誰，這就是問題。

但是根據(jù)題意，我們可以發(fā)現(xiàn)：揭發(fā)狼人的和狼人所指的都是平民，這不就有點像無向圖的關(guān)系嘛~每人揭發(fā)一人，構(gòu)成基環(huán)樹，可以找出來環(huán)然后每個環(huán)內(nèi)的節(jié)點作為根節(jié)點，找出來根節(jié)點作狼人和作平民時的最大狼人數(shù)量。這里其實就是一個樹形的動態(tài)規(guī)劃（雖然做題的時候我并沒有意識到，但我寫出來了），先將子樹根節(jié)點作狼人/平民時候的狼人最大數(shù)量算出來，然后在上一個根節(jié)點得出同類型的兩個值，葉子節(jié)點上作為狼人時狼人數(shù)量是1，不做狼人時狼人數(shù)量是0，上一級節(jié)點如果作為平民，則下級節(jié)點既可以是狼人也可以是平民，因此我們?nèi)蓚€值中的最大值，如果作為狼人，則下一個節(jié)點只能取平民，然后狼人數(shù)量再+=1（因為上級節(jié)點作為狼人的數(shù)量應(yīng)該計入）以此類推，直到環(huán)上的節(jié)點的最大狼人數(shù)量都被算出來，這道題就做出來了一大半。

然后我們手里就拿到了一個大概率不算很長，數(shù)據(jù)已經(jīng)算好的環(huán)。這個時候我們根據(jù)狼人和狼人不能相鄰的特性，隨機切斷這個環(huán)，再將任意一個端點作為樹的根節(jié)點，而這個節(jié)點會被確定為平民，這樣環(huán)中的上一個節(jié)點的種類就不再受到限制了。繼續(xù)轉(zhuǎn)移方程，最后在根節(jié)點中作為平民，得出一個ans_a。

那么如果真正的最優(yōu)方案中根節(jié)點應(yīng)該做狼人應(yīng)該怎么辦呢？很簡單，因為如果這個點是狼人那么旁邊的點一定是平民，因此在將環(huán)中的根節(jié)點錯位一下，將旁邊得點當(dāng)成平民重復(fù)上一段的運算一遍，取兩個方案中答案的最大值加在ans里，在程序考慮所有點后輸出。

最后在提醒一點：本題和上一道題一樣，存在兩個子圖不連通的情況，針對這種情況需要染色+循環(huán)找到未被設(shè)計的點，因此不少程序段會重復(fù)進行，數(shù)組數(shù)據(jù)需要注意清空。

放上代碼，這道題的代碼我保守估計和上一個代碼的查重率會在50%以上，剩下的代碼寫出來不多，不過挺費腦力，少一個環(huán)節(jié)都會爆蛋；