Codeforces Round #790 (Div. 4) 1676G. White-Black Balanced Subtrees Solution

 Problem  Link  :    https://codeforces.com/problemset/problem/1676/G

Solution in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

const int N = 4e4 + 9;

vector<ll> adj[N];

bool vis[N];

string s;

ll blacknode[N], whitenode[N];

void dfs(int node) {

  vis[node] = true;

  ll black = 0, white = 0;

  if (s[node - 1] == 'W')

    white++;

  else

    black++;

  for (int i = 0; i < adj[node].size(); i++) {

    int next = adj[node][i];

    if (!vis[next]) dfs(next);

    white += whitenode[next];

    black += blacknode[next];

  }

  blacknode[node] = black;

  whitenode[node] = white;

}

int main() {

  ios_base::sync_with_stdio(0);

  cin.tie(0);

  ll t;

  cin >> t;

  while (t--) {

    int n;

    cin >> n;

    for (int i = 1; i <= n; i++) {

      adj[i].clear();

      vis[i] = false;

      blacknode[i] = whitenode[i] = 0;

    }

    for (int i = 2; i <= n; i++) {

      int x;

      cin >> x;

      adj[x].push_back(i);

    }

    cin >> s;

    dfs(1);

    ll cn = 0;

    for (int i = 1; i <= n; i++) {

      if (blacknode[i] == whitenode[i]) cn++;

    }

    cout << cn << endl;

  }

}