题意：

在狼人杀里，有三种类型的人，一种是狼人，一种是村民，还有一种是不确定身份的人。已知村民不会撒谎，狼人可能会撒谎。每个人都会说一句话，比如玩家x是狼人或者玩家x是村民，自己不会说自己。问狼人和村民各有几人。其中$1≤T≤10,1≤N≤100000$。

思路：

在比赛的时候思路在经过把本来的想法的叉掉的过程之后是对了，然而不会写…

因为无论说什么全部人都是狼的情况都肯定是成立的，所以不存在确定的村民。

考虑两个人成环的时候，只有当1说2是v，2说1是w的时候能确定1是狼人。考虑三个人成环的时候，只有当1说2是v，2说3是v，3说w的时候能确定1是狼人。所以对于每个环，当只存在一条狼边的时候，这条狼边指向的人是狼人。

说确定的狼人是村民的人肯定在说谎，所以说狼人是村民的人肯定也是狼人。

写的时候有点麻烦啊…直接写对于标记的处理有点搞不清楚…

网上搜题解有用缩点做的，用缩点来处理环的确是好写一点。

缩点后得到一些强连通分量，统计每个强连通分量的结点数和狼边的条数（遍历每个人的出边，如果是狼边，它所在的强连通分量狼边条数++），如果点数大于等于2并且狼边只有一条，说明狼边指向的就是狼人，标记为狼人，然后对于每个确定的狼人，搜说他是村民的人（反向存边），那些人也是狼人。

这样复杂度也是可以的，是$O(n+n)$。

代码：

struct node
{
    int to,val;
}v[100010];
vector<int>rv[100010];
int dfn[100010];//在DFS中该节点被搜索的次序
int low[100010];//i或i的子树能够通过非树边追溯到最早的祖先节点（即DFS次序号最小）
int sccn[100010];//缩点数组，表示某个点对应的强连通分量编号
bool vis[100010];//是否在栈中
int num[100010];//编号为i的强连通分量中点的数量
int w[100010];//编号为i的强连通分量中狼边的数量
int id[100010];//编号为i的强连通分量中狼的编号
int tp[100010];//身份
int step;
int cnt;//强连通分量编号
stack<int>s;
void tarjan(int u)
{
    dfn[u]=low[u]=++step;
    vis[u]=true;
    s.push(u);
    int temp=v[u].to;
    if(!dfn[temp])//没有被访问过
    {
        tarjan(temp);
        low[u]=min(low[u],low[temp]);
    }
    else if(vis[temp])//在栈中
        low[u]=min(low[u],dfn[temp]);
    if(low[u]==dfn[u])//构成强连通分量
    {
        cnt++;
        while(1)
        {
            int temp=s.top();
            s.pop();//此点以上的点全部出栈，构成一个强连通分量
            vis[temp]=false;
            sccn[temp]=cnt;//cnt是强连通分量的序号
            if(temp==u)break;
        }
    }
}
void dfs(int cur)
{
    int len=rv[cur].size();
    for(int i=0;i<len;i++)
    {
        if(tp[rv[cur][i]]==-1)
        {
            tp[rv[cur][i]]=0;
            dfs(rv[cur][i]);
        }
    }
}
int main()
{
    int t,n,x;
    char s[20];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            rv[i].clear();
            dfn[i]=sccn[i]=num[i]=w[i]=id[i]=0;
            vis[i]=false;
            tp[i]=-1;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            scanf("%s",s);
            if(s[0]=='w')
                v[i]=node{x,0};//狼边
            else if(s[0]=='v')
            {
                v[i]=node{x,1};
                rv[x].push_back(i);
            }
        }
        step=cnt=0;
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i);
        for(int i=1;i<=n;i++)
            num[sccn[i]]++;
        for(int i=1;i<=n;i++)
        {
            if(v[i].val==0)
            {
                w[sccn[i]]++;
                id[sccn[i]]=v[i].to;
            }
        }
        for(int i=1;i<=cnt;i++)
        {
            if(num[i]>=2&&w[i]==1)
            {
                tp[id[i]]=0;
                dfs(id[i]);
            }
        }
        int ans1=0,ans2=0;
        for(int i=1;i<=n;i++)
        {
            if(tp[i]==0)ans2++;
            else if(tp[i]==1)ans1++;
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}