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

WYF互相追逐的头

题目的阅读量比较大，而且数据比较清奇，但是我们可以知道的是每一个头都在尽力追逐自己喜欢的那个头，因此和它同方向（也就是不知道往哪移动）必然就是早晚的事情。

所以如果互相追逐的头之间的追逐关系形成一个环的话，WYF的这些头到最后必然会不知道往哪去，因此只要我们能够判环，则此题可以解之。

但是我们在解题的时候要注意一点：输入的数据描述种存在一种可能性，使得两群头之间不存在任何追逐的关系，针对这种情况，解决方案就是将联通的节点之间打上标记，然后没有被标记的节点再次进行判环，其实只要找到了一个环就立刻输出即可，这道题特判，判分很松。

下放代码，代码量两题都很大，但是MAFIJA的部分代码可以完全抄WYF的头的。

MAFIJA

简单聊一下题意和本质。狼人和民众数量未知，每个人之间互相揭发，狼人知道谁是什么角色，因此不会揭发同伙，平民则是在随机揭发，他们的揭发没有任何价值。

由此可见我们可以忽略平民的揭发，狼人揭发的一定是平民，但是我们现在并不知道狼人和平民谁是谁，这就是问题。

但是根据题意，我们可以发现：揭发狼人的和狼人所指的都是平民，这不就有点像无向图的关系嘛~每人揭发一人，构成基环树，可以找出来环然后每个环内的节点作为根节点，找出来根节点作狼人和作平民时的最大狼人数量。这里其实就是一个树形的动态规划（虽然做题的时候我并没有意识到，但我写出来了），先将子树根节点作狼人/平民时候的狼人最大数量算出来，然后在上一个根节点得出同类型的两个值，叶子节点上作为狼人时狼人数量是1，不做狼人时狼人数量是0，上一级节点如果作为平民，则下级节点既可以是狼人也可以是平民，因此我们取两个值中的最大值，如果作为狼人，则下一个节点只能取平民，然后狼人数量再+=1（因为上级节点作为狼人的数量应该计入）以此类推，直到环上的节点的最大狼人数量都被算出来，这道题就做出来了一大半。

然后我们手里就拿到了一个大概率不算很长，数据已经算好的环。这个时候我们根据狼人和狼人不能相邻的特性，随机切断这个环，再将任意一个端点作为树的根节点，而这个节点会被确定为平民，这样环中的上一个节点的种类就不再受到限制了。继续转移方程，最后在根节点中作为平民，得出一个ans_a。

那么如果真正的最优方案中根节点应该做狼人应该怎么办呢？很简单，因为如果这个点是狼人那么旁边的点一定是平民，因此在将环中的根节点错位一下，将旁边得点当成平民重复上一段的运算一遍，取两个方案中答案的最大值加在ans里，在程序考虑所有点后输出。

最后在提醒一点：本题和上一道题一样，存在两个子图不连通的情况，针对这种情况需要染色+循环找到未被设计的点，因此不少程序段会重复进行，数组数据需要注意清空。

放上代码，这道题的代码我保守估计和上一个代码的查重率会在50%以上，剩下的代码写出来不多，不过挺费脑力，少一个环节都会爆蛋；