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;
  }
}


No comments

Most View Post

Recent post

Codeforces Round 971 (Div. 4) 2009C. The Legend of Freya the Frog Solution

  Problem Link    https://codeforces.com/contest/2009/problem/C S olution in C++: /// Author : AH_Tonmoy #include < bits / stdc ++. h ...

Powered by Blogger.