[Codeforces] E. Danil and a Part-time Job

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Danil and a Part-time Job
Source            : Codeorces
Category          : Graph Theory, Data Structure
Algorithm         : Euler tour on Tree, Segment Tree, Lazy Propagation
Verdict           : Accepted

 
#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 2e5 + 5;
 
struct segmentTree
{
      int on, off;
      bool toggle;
      inline void assignLeaf(const int t)
      {
            on = off = toggle = 0;
            t ? on += 1 : off += 1;
      }
      inline void marge(const segmentTree &l, const segmentTree &r)
      {
            on = l.on + r.on;
            off = l.off + r.off;
      }
      inline void doSwap()
      {
            swap(on, off);
      }
} tree[maxn << 2];
 
vector <int> graph[maxn];
int t[maxn];
int in[maxn], out[maxn], which[maxn];
int dfsTime;
 
inline void build(int node, int a, int b)
{
      tree[node].toggle = 0;
      if (a == b)
      {
            tree[node].assignLeaf(t[ which[a] ]);
            return;
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      build(lft, a, mid);
      build(rgt, mid+1, b);
      tree[node].marge(tree[lft], tree[rgt]);
}
 
inline void doToggle(int node, int a, int b)
{
      if (tree[node].toggle == 0) return;
      tree[node].doSwap();
      if (a != b)
      {
            int lft = node << 1;
            int rgt = lft | 1;
            tree[lft].toggle ^= 1;
            tree[rgt].toggle ^= 1;
      }
      tree[node].toggle = 0;
}
 
inline void rangeUpdate(int node, int a, int b, int i, int j)
{
      doToggle(node, a, b);
      if (a > b || a > j || b < i) return;
      if (a >= i && b <= j)
      {
            tree[node].doSwap();
            if (a != b)
            {
                  int lft = node << 1;
                  int rgt = lft | 1;
                  tree[lft].toggle ^= 1;
                  tree[rgt].toggle ^= 1;
            }
            return;
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      rangeUpdate(lft, a, mid, i, j);
      rangeUpdate(rgt, mid+1, b, i, j);
      tree[node].marge(tree[lft], tree[rgt]);
}
 
inline int rangeQuery(int node, int a, int b, int i, int j)
{
      doToggle(node, a, b);
      if (a > b || a > j || b < i) return 0;
      if (a >= i && b <= j) return tree[node].on;
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      int p = rangeQuery(lft, a, mid, i, j);
      int q = rangeQuery(rgt, mid+1, b, i, j);
      return p + q;
}
 
inline void eulerPath(int u = 1, int p = -1)
{
      in[u] = ++dfsTime;
      which[dfsTime] = u;
      for (int v : graph[u])
      {
            if (v == p) continue;
            eulerPath(v, u);
      }
      out[u] = dfsTime;
}
 
inline int read()                   { int a; scanf("%d", &a); return a; }
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int n = read();
      for (int v = 2; v <= n; v++)
      {
            int u = read();
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
      }
      for (int i = 1; i <= n; i++) t[i] = read();
      eulerPath();
      build(1, 1, n);
      int q = read();
      char type[6];
      int p;
      while (q--)
      {
            scanf("%s %d", type, &p);
            if (type[0] == 'g')
            {
                  int tOn = rangeQuery(1, 1, n, in[p], out[p]);
                  printf("%d\n", tOn);
            }
            else
            {
                  rangeUpdate(1, 1, n, in[p], out[p]);
            }
      }
}