分析题目
首先将题面抽象成模型，以指证关系为边，玩家为点，条边个点构成基环树森林。边有方向，基环树为内向树。
狼人指证的一定是平民，平民指证无特殊限制，由此可以看出若一个人是狼人，指证他的人和他指证的人都不是狼人。即狼人在图上不能连续出现。
现在，问题变成了，在一个基环树森林中最多能选取多少不相邻的点。即基环树最大独立集问题
设计方案
考虑在基环树上的DP
- 第一步
找出环，可以通过DFS实现，从一个未被访问的节点开始，没经过一个点就将其放入栈中。若到达一个已经在栈中的节点，那么就找到了一个环。弹出栈顶直到弹出当前所在的节点，弹出的节点构成一个环。
- 第二步
对于环上的每一个节点，考虑以它为根节点的树，最多能选取多少不相邻的点。问题在此转化为树形DP。
对于树上的任意一点，若选取它，可取到的最大节点数为不选其儿子节点能取到的最大节点数之和。若不选取它，可取到的最大节点数为选取或不选取其儿子节点的最大值之和。
最后我们可以求出，对于环上任意一点和以其为根的树中，选取环上的点或不选取环上的点能取得的最大节点数。
- 第三步
现在，问题变为了在一个环上，对于任意一个节点，选取它有一个价值，不选取它有另一个价值，选取的节点不能相邻，求能取得的最大值。
我们不妨以环中的1号元素为分界线，将环断开，对于每一个节点，可以取或不取。同时需要注意的是，如果选取了1号元素，就不能选取n号元素。
由此我们可以定义f[i][j][k]代表对于前个元素，第元素取()或不取()，是否选取第一个元素(即选取即不选取），所能取得的最大值。
具体转移方法见题库中的 《圆环独立集》问题
- 第四步
重复上述操作，对每一颗基环树进行求值，总和就是答案。