题目的主要信息：

• 没有回路的无向连通图，可以看成树，根结点为1
• 其中一部分结点染成了红色
• 之后有$qq$次询问，每次询问以该结点作为根的子树有多少红色结点

具体做法：

根据输入的父节点，构建树的邻接表。

然后用字符串记录输入的染色信息，再通过dfs构建，对树进行染色，构建dp数组。其中$dp[i]dp[i]$表示以第i个结点为根的子树红色结点个数，我们在dfs的时候，$dp[i]dp[i]$首先等于这个结点本身有无染色，然后遍历这个结点的所有子结点，得到所有子树，所有子树的染色结点数和就是以这个结点为子树的染色结点数，最后更新dp数组，返回即可。

查询的时候，直接访问dp数组即可。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int dfs(int x, string& s, vector<int>& dp, vector<vector<int>>& G){
    int count = 0;
    if(s[x - 1] == 'R') ///字符串下标往前移一位才是对应结点
        count++; //记录该结点
    for(int i = 0; i < G[x].size(); i++) //统计该结点子树染色个数
        count += dfs(G[x][i], s, dp, G);
    return dp[x] = count;  //更新dp数组
}

int main(){
    int n;
    cin >> n;
    vector<vector<int>> G(n + 1); //树的邻接表
    for(int i = 1; i < n; i++){
        int temp;
        cin >> temp; //输入后续结点的父节点
        G[temp].push_back(i + 1); //父节点上连接该结点
    }
    string s;
    cin >> s; //输入染色信息
    vector<int> dp(n + 1, 0); //dp[i]表示以第i个结点为根的子树红色结点个数
    dfs(1, s, dp, G); //dfs构建dp数组
    int q;
    cin >> q;
    while(q--){ //q次查询
        int temp;
        cin >> temp;
        cout << dp[temp] << endl; //直接访问数组
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n+q)O(n+q)$，最坏遍历$nn$个结点构建dp数组，然后$qq$询问都是直接访问数组
• 空间复杂度：$O(n)O(n)$，dp数组及邻接表最大空间为$nn$