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

Bismillahir Rahmanir Rahim

///Author: Tanvir Ahmmad

///CSE,Islamic University,Bangladesh

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<iterator>

#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array

/*every external angle sum=360 degree

  angle find using polygon hand(n) ((n-2)*180)/n*/

///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b

using namespace std;

typedef long long ll;

const int N=1e5;

vector<ll>g[N];

bool vis[N];

string str;

ll blacknode[N],whitenode[N];

void dfs(ll node)

{

    vis[node]=true;

    ll black=0,white=0;

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

        white++;

    else

        black++;

    for(ll i=0; i<g[node].size(); i++)

        if(vis[g[node][i]]==false)

        {

            dfs(g[node][i]);

            black+=blacknode[g[node][i]];

            white+=whitenode[g[node][i]];

        }

    blacknode[node]=black;

    whitenode[node]=white;

}

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    ll tst,node,num;

    cin>>tst;

    while(tst--)

    {

        cin>>node;

        for(ll i=1;i<=node;i++)

            blacknode[i]=whitenode[i]=0,vis[i]=false,g[i].clear();

        for(ll i=2; i<=node; i++)

            cin>>num,g[num].push_back(i);

        cin>>str;

        dfs(1);

        ll cnt=0;

        for(ll i=1;i<=node;i++)

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

        cout<<cnt<<endl;

    }

    return 0;

}

///Alhamdulillah

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