题解 | #小红的树#

dp[i]:以第i个节点为根节点的子树的染色个数。 tree[i]:为第i个节点的父亲节点。 先获取树，然后为需要染色的节点赋值dp[i]=1，最后从第n个节点依次往前逐次把dp[i]增加到dp[tree[i]]上。

dp[tree[i]]+=dp[i];

#include<iostream>
using namespace std;

int main(){
    int n,q;
    int tree[101010]={0};
    int dp[101010]={0};
    char c;
    cin>>n;
    tree[0]=n;
    tree[1]=-1;
    for(int i=2;i<=n;++i){
        cin>>tree[i];
    }
    for(int i=1;i<=n;++i){
        cin>>c;
        if(c=='R'){
            dp[i]=1;
        }
    }
    for(int i=n;i>1;--i)
        dp[tree[i]]+=dp[i];
    cin>>q;
    while(q--){
        int i;
        cin>>i;
        cout<<dp[i]<<endl;
    }
    return 0;
}

时间复杂度：O(n+q) 空间复杂度：O(n)