小红的树

难度：2星

树形dp模板题。我们先预处理出每个节点子树的红色节点的数量。定义 $dp[i]dp[i]$ 为以 $ii$ 为根的子树的红色节点的数量，那么转移方程是：

$dp[i]={\sum }_{x\mathrm{是}i\mathrm{的}\mathrm{孩}\mathrm{子}}dp[x]+[i\mathrm{为}\mathrm{红}\mathrm{点}]dp[i]=\backslash sum\_\{x是i的孩子\}dp[x]+[i为红点]$

只需要在dfs的时候进行转移即可。

#include<bits/stdc++.h>
using namespace std;
vector<int>g[100020];
int dp[100010];
string s;
int dfs(int x){
    int i,sum=s[x-1]=='R';
    for(i=0;i<g[x].size();i++){
        sum+=dfs(g[x][i]);
    }
    return dp[x]=sum;
}
int main(){
    int n,i;
    cin>>n;
    for(i=2;i<=n;i++){
        int x;
        cin>>x;
        g[x].push_back(i);
    }

    cin>>s;
    dp[1]=dfs(1);
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        cout<<dp[x]<<endl;
    }

}