原题链接

题解

细节很多的树形dp，请看代码

code

#define ll long long
#include<bits/stdc++.h>
using namespace std;
ll sit[100005]={0};
ll f[100005]={0};
vector<ll> G[100005];
char str[100005];

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

void ss(ll now)
{

    ll p=0,s=0,c=0;
    f[now]=0;
    for(auto next:G[now])
    {
        ss(next);
        if(sit[next]==1) p++;
        else if(sit[next]==0) c++;
        else s++;
        f[now]+=f[next];
    }

    //以下为核心部分
    if(str[now]=='P')
    {
        sit[now]=1;
        f[now]+=s;
    }
    else if(str[now]=='S')
    {
        sit[now]=-1;
        f[now]+=p;
    }
    else
    {
        if(!s&&!p) sit[now]=0;//如果子节点只有C不需要造墙
        else
        {
            if(s>p)
            {
                sit[now]=-1;
                f[now]+=p;
            }
            else if(p>s)
            {
                sit[now]=1;
                f[now]+=s;
            }
            else
            {
                //头节点为C，我给p建墙；头节点为s，我给p建墙，头节点为p，我给s建墙。最后浓缩成下面这个式子
                sit[now]=0;
                f[now]+=s;
            }
        }
    }
}

int main()
{
    ll t;
    read(t);
    while(t--)
    {
        ll n;
        read(n);
        for(ll i=2;i<=n;i++)
        {
            ll x;
            read(x);
            G[x].push_back(i);
        }

        scanf("%s",str+1);
        ss(1);

        write(f[1]);
        putchar('\n');

        for(ll i=1;i<=n;i++)G[i].clear();
        memset(sit,0,sizeof sit);
    }
    return 0;
}