fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct SegTree {
  5.   vector<int> node, lazy;
  6.  
  7.   SegTree(int n) : node(n << 1), lazy(n << 1) {}
  8.  
  9.   void update(int i, int l, int r, int a, int b, int v) {
  10.     if (l > b || r < a) {
  11.       return;
  12.     } else if (l >= a && r <= b) {
  13.       return flip(i, v);
  14.     }
  15.     int m = (l + r) >> 1;
  16.     int x = i + 1;
  17.     int y = i + ((m - l + 1) << 1);
  18.     propagate(i, x, y);
  19.     update(x, l, m + 0, a, b, v);
  20.     update(y, m + 1, r, a, b, v);
  21.     node[i] = node[x] ^ node[y];
  22.   }
  23.  
  24.   void flip(int i, int v) {
  25.     node[i] ^= v;
  26.     lazy[i] ^= v;
  27.   }
  28.  
  29.   void propagate(int i, int x, int y) {
  30.     flip(x, lazy[i]);
  31.     flip(y, lazy[i]);
  32.     lazy[i] = 0;
  33.   }
  34.  
  35.   int query(int i, int l, int r, int a, int b) {
  36.     if (l > b || r < a) {
  37.       return 0;
  38.     } else if (l >= a && r <= b) {
  39.       return node[i];
  40.     }
  41.     int m = (l + r) >> 1;
  42.     int x = i + 1;
  43.     int y = i + ((m - l + 1) << 1);
  44.     propagate(i, x, y);
  45.     return query(x, l, m + 0, a, b) ^ query(y, m + 1, r, a, b);
  46.   }
  47. };
  48.  
  49. int main() {
  50.   ios::sync_with_stdio(false);
  51.   cin.tie(0);
  52.   int n, q;
  53.   cin >> n;
  54.   vector<vector<int>> adj(n);
  55.   for (int i = 1; i < n; ++i) {
  56.     int u, v;
  57.     cin >> u >> v;
  58.     --u, --v;
  59.     adj[u].push_back(v);
  60.     adj[v].push_back(u);
  61.   }
  62.   int timer = -1;
  63.   vector<int> in(n), out(n);
  64.   function<void(int, int)> dfs = [&](int u, int p) {
  65.     in[u] = ++timer;
  66.     for (int v : adj[u]) {
  67.       if (v != p) {
  68.         dfs(v, u);
  69.       }
  70.     }
  71.     out[u] = ++timer;
  72.   };
  73.   dfs(0, -1);
  74.   SegTree tree(out[0] + 1);
  75.   cin >> q;
  76.   while (q--) {
  77.     int t;
  78.     cin >> t;
  79.     if (t == 1) {
  80.       int u, v;
  81.       cin >> u >> v;
  82.       --u;
  83.       tree.update(0, in[0], out[0], in[u], out[u], v);
  84.     } else {
  85.       int u;
  86.       cin >> u;
  87.       --u;
  88.       cout << tree.query(0, in[0], out[0], in[0], in[u]) << "\n";
  89.     }
  90.   }
  91.   return 0;
  92. }
  93.  
Success #stdin #stdout 0s 4788KB
comments (?)
stdin
copy 
6
1 2
1 6
2 4
4 3
5 4
7
2 3
1 2 7
2 3
2 6
1 4 4
2 4
2 1
stdout
copy 
0
7
0
4
0
https://ideone.com/ptDoX6
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!