思路
发现权值为 C 的点可以选择看做是权值为 S 或为 P 的点，所以问题转换为怎么给 C 点赋值可以使答案最小，考虑树形 dp。
\(f_{i,0/i,1}\) 表示 \(i\) 点赋值为 S 或 P 时最少要删除几条边。但如果当前点权值不为 C 的话，那显然他的父亲节点应该选择和他权值相同的点才最优，所以可以把权值相反时的 \(f_i\) 赋值为一个很大的数，这样就不会被选择了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
inline int read();
int T,n,a[N],cnt,head[N],f[N][2];
bool vis[N];
struct E{
int to,next;
}edge[N<<1];
void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int x)
{
vis[x]=1;
for(int i=head[x];i;i=edge[i].next)
{
int to=edge[i].to;
if(vis[to]) continue;
dfs(to);
f[x][0]+=min(f[to][0],f[to][1]+1);
f[x][1]+=min(f[to][1],f[to][0]+1);
}
if(a[x]==1) f[x][0]=inf;
else if(a[x]==-1) f[x][1]=inf;
}
int main()
{
T=read();
for(int d=1;d<=T;d++)
{
cnt=0;
memset(head,0,sizeof head);
memset(a,0,sizeof a);
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++) f[i][0]=f[i][1]=0;
n=read();
for(int i=2;i<=n;i++)
{
int x;
x=read();
add(i,x);
add(x,i);
}
for(int i=1;i<=n;i++)
{
char ch;
cin>>ch;
if(ch=='S') a[i]=1;
else if(ch=='P') a[i]=-1;
}
dfs(1);
printf("%d\n",min(f[1][0],f[1][1]));
}
return 0;
}
inline int read()
{
int x=0,f=1;
char ch;
ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch&15);
ch=getchar();
}
return x*f;
}