题目描述

难度分:$1900$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n(2 \leq n \leq 10^5)$和$n-1$个数$a_2,a_3,…,a_n(1 \leq a_i \lt i)$，表示节点 $i$和节点$a_i$之间有一条无向边。

这$n-1$条无向边形成了一棵树，节点编号从$1$到$n$。

然后输入长为$n$的字符串$s$，只包含字母P、S、C，表示节点$i$的类型是$s[i]$。

最少要切断多少条边，使得类型为P的节点都无法到达任意类型为S的节点？

输入样例

3
3
1 1
CSP
4
1 2 2
PCSS
4
1 2 2
PPSS

输出样例

1
1
2

算法

树形DP

状态定义

$dp[u][t]$表示以$u$为根的子树合法的情况下，最上面有影响的节点状态为$t$时，子树$u$中删除的最少边。其中$t=0$说明子树$u$无法向上传播声音；$t=1$说明子树$u$可以向上传播声音。

状态转移

对于任意一个节点$u$，它和子节点$v$的状态就决定了它们之间是否要删边。

如果$s[v]=$P，说明子树$v$中有$party$的声音会传上来，分$2$种情况：

1. 子树$u$要求无法传播声音出去，则有状态转移$dp[u][0]=\Sigma_{v,s[v]=P}dp[v][1]+1$。
2. 子树$u$可以允许声音传播出去，则有状态转移$dp[u][1]=\Sigma_{v,s[v]=P}dp[v][1]$。

如果$s[v]=$S，说明子树$v$肯定没有声音传上来，否则会吵到$v$睡觉，分$2$种情况：

1. 子树$u$要求无法传播声音出去，则有状态转移$dp[u][0]=\Sigma_{v,s[v]=S}dp[v][0]$。
2. 子树$u$可以允许声音传播出去，则有状态转移$dp[u][1]=\Sigma_{v,s[v]=S}dp[v][0]+1$，$u$和$v$之间要加隔音墙，否则$u$的声音会影响$v$睡觉。

这里还需要判断一下，如果$s[u]=$S，子树$u$最上面的节点是睡觉的，没有声源向上传播声音，此时$dp[u][1]$是无效的。如果$s[u]=$P，子树$u$最上面的节点是开$party$的，无法阻止声音网上传播，此时$dp[u][0]$是无效的。

最终答案就是$dp[1]$的状态，取决于$s[1]$的取值。如果$s[1]=$P，那根节点就有声音，答案为$dp[1][1]$；如果$s[1]=$S，那根节点处必须安静，答案为$dp[1][0]$；否则答案就是$dp[1][0]$和$dp[1][1]$的较小值。

复杂度分析

时间复杂度

需要遍历整棵树来完成树形DP，因此时间复杂度为$O(n+m)$，其中$n$为节点数，$m$为边数，而树中$m=n-1$，边数和节点数是一个级别的，整个算法的时间复杂度为$O(n)$。

空间复杂度

树的邻接表额外空间复杂度为$O(n)$，DP的状态数量为$3n$，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010, INF = 0x3f3f3f3f;
int t, n, a[N], dp[N][2];
char s[N];
vector<int> graph[N];

void dfs(int u, int fa) {
    dp[u][0] = dp[u][1] = 0;
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs(v, u);
        if(s[v] == 'C') {
            dp[u][0] += min(dp[v][0], dp[v][1] + 1);
            dp[u][1] += min(dp[v][0] + 1, dp[v][1]);
        }else if(s[v] == 'S') {
            dp[u][0] += dp[v][0];
            dp[u][1] += dp[v][0] + 1;
        }else {
            dp[u][0] += dp[v][1] + 1;
            dp[u][1] += dp[v][1];
        }
    }
    if(s[u] == 'P') dp[u][0] = INF;
    if(s[u] == 'S') dp[u][1] = INF;
}

void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
    }
    for(int i = 2; i <= n; i++) {
        scanf("%d", &a[i]);
        graph[i].push_back(a[i]);
        graph[a[i]].push_back(i);
    }
    scanf("%s", s + 1);
    dfs(1, 0);
    int res = s[1] == 'P'? dp[1][1]: (s[1] == 'S'? dp[1][0]: min(dp[1][0], dp[1][1]));
    printf("%d\n", res);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        solve();
    }
    return 0;
}