Advertisement
ivnikkk

Untitled

May 10th, 2022
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS  
  2. #define debug(l) cerr<<#l<<' '<<l<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(a) a.begin(), a.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef long double ld;
  9. vector<vector<ll>> gr;
  10. vector<vector<ll>> siz;
  11. vector<ll> clr;
  12. ll ans = 0;
  13. void dfs(ll v, ll p) {
  14.     siz[clr[v]][v] = 1;
  15.     for (ll& u : gr[v]) {
  16.         if (u != p) {
  17.             dfs(u, v);
  18.             siz[0][v] += siz[0][u];
  19.             siz[1][v] += siz[1][u];
  20.         }
  21.     }
  22.     if (siz[1][v] == siz[0][v])ans++;
  23. }
  24. signed main() {
  25. #ifdef _DEBUG
  26.     freopen("input.txt", "r", stdin);
  27.     freopen("output.txt", "w", stdout);
  28. #endif
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(nullptr);
  31.     cout.tie(nullptr);
  32.     ll t;
  33.     cin >> t;
  34.     while (t--) {
  35.         ans = 0;
  36.         ll n;
  37.         cin >> n;
  38.         gr.clear();
  39.         siz.clear();
  40.         gr.resize(n);
  41.         siz.resize(2, vector<ll>(n, 0));
  42.         clr.resize(n);
  43.         for (ll i = 0; i < n - 1; i++) {
  44.             ll x;
  45.             cin >> x;
  46.             x--;
  47.             gr[x].push_back(i + 1);
  48.             gr[i + 1].push_back(x);
  49.         }
  50.         string s;
  51.         cin >> s;
  52.         for (ll i = 0; i < s.size(); i++) {
  53.             if (s[i] == 'B') {
  54.                 clr[i] = 1;
  55.             }
  56.             else {
  57.                 clr[i] = 0;
  58.             }
  59.         }
  60.         dfs(0,-1);
  61.         cout << ans << '\n';
  62.     }
  63.  
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement