题解 | 小红的树

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
#include <iostream>
#include <vector>
using namespace std;

const int nn = static_cast<int>(1e5 + 10);
vector<int> a[nn];//----------存储子节点
int ans[nn]{0};//------------存储每个节点的答案

void dfs(int node){//---------dfs
  size_t size = a[node].size();
  for(int i = 0; i < size; i++){//--------遍历每个子节点
    int son = a[node][i];
    dfs(son);
    ans[node] += ans[son];//-----当前节点作为根的树的答案是其子节点作为根的答案的总和
  }
}

int main(){
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  int n;
  int x;
  cin >> n;
  for (int i = 0; i < n - 1; i++){
    cin >> x;
    a[x].push_back(i + 2);
  }
  string s;
  cin >> s;
  for (int i = 0; i < n; i++)
    if (s[i] == 'R')
      ans[i + 1] = 1;//-----初始化一下
  dfs(1);
  int q;
  cin >> q;
  while(q--){
    cin >> x;
    cout << ans[x] << '\n';
  }
  return 0;
}