fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FILE "SHIP"
  4.  
  5. #define int long long
  6. #define ii pair<int, int>
  7.  
  8. #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9. #define FOR(I, L, R) for(int I = (int)L; I <= (int)R; I++)
  10. #define FOD(I, R, L) for(int I = (int)R; I >= (int)L; I--)
  11. #define FOA(I, A) for(auto &I : A)
  12.  
  13. #define all(A) A.begin(), A.end()
  14. #define fi first
  15. #define se second
  16.  
  17. const int N = 2e5 + 10;
  18. const int oo = 1e18;
  19. const int mod = 1e9 + 7;
  20.  
  21. int n, q;
  22. int a[N];
  23. vector<int> g[N];
  24.  
  25. struct segment{
  26.      int seg[N << 2], lazy[N << 2];
  27.  
  28.      segment(){
  29.           memset(seg, 0, sizeof seg);
  30.           memset(lazy, 0, sizeof lazy);
  31.      }
  32.  
  33.      void push_down(int id, int l, int r){
  34.           int m = (l + r) >> 1;
  35.           seg[id << 1] = m - l + 1 - seg[id << 1];
  36.           seg[id << 1 | 1] = r - m - seg[id << 1 | 1];
  37.  
  38.           lazy[id << 1] ^= lazy[id];
  39.           lazy[id << 1 | 1] ^= lazy[id];
  40.           lazy[id] = 0;
  41.      }
  42.  
  43.      void update(int id, int l, int r, int u, int v){
  44.           if(v < l || r < u) return;
  45.           if(u <= l && r <= v){
  46.                seg[id] = r - l + 1 - seg[id];
  47.                lazy[id] ^= 1;
  48.  
  49.                return;
  50.           }
  51.  
  52.           push_down(id, l, r);
  53.           int mid = (l + r) >> 1;
  54.  
  55.           update(id << 1, l, mid, u, v);
  56.           update(id << 1 | 1, mid + 1, r, u, v);
  57.  
  58.           seg[id] = seg[id << 1] + seg[id << 1 | 1];
  59.      }
  60.  
  61.      int get(int id, int l, int r, int u, int v){
  62.           if(v < l || r < u) return 0;
  63.           if(u <= l || r <= v) return seg[id];
  64.  
  65.           push_down(id, l, r);
  66.           int mid = (l + r) >> 1;
  67.  
  68.           int s1 = get(id << 1, l, mid, u, v);
  69.           int s2 = get(id << 1 | 1, mid + 1, r, u, v);
  70.  
  71.           return s1 + s2;
  72.      }
  73. }sg;
  74.  
  75. int cnt;
  76. int tour[N], in[N], out[N];
  77.  
  78. void euler(int u, int p){
  79.      tour[++cnt] = u;
  80.      in[u] = cnt;
  81.  
  82.      if(a[u]) sg.update(1, 1, n, cnt, cnt);
  83.  
  84.      FOA(v, g[u]) if(v != p){
  85.           euler(v, u);
  86.      }
  87.  
  88.      out[u] = cnt;
  89. }
  90.  
  91. signed main(){ fast
  92.      if(fopen(FILE ".INP", "r")){
  93.           freopen(FILE".INP", "r", stdin);
  94.           freopen(FILE".OUT", "w", stdout);
  95.      }
  96.  
  97.      cin >> n;
  98.      FOR(v, 2, n){
  99.           int u; cin >> u;
  100.           g[u].push_back(v);
  101.           g[v].push_back(u);
  102.      }
  103.      FOR(i, 1, n) cin >> a[i];
  104.      euler(1, 0);
  105.  
  106.      cin >> q;
  107.      while(q--){
  108.           int t, u;
  109.           cin >> t >> u;
  110.           t--;
  111.  
  112.           if(t){
  113.                cout << sg.get(1, 1, n, in[u], out[u]) << '\n';
  114.           }else{
  115.                sg.update(1, 1, n, in[u], out[u]);
  116.           }
  117.      }
  118. }
  119.  
Success #stdin #stdout 0.01s 24004KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/1Pu3Oo
language:
C++ (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!