fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. typedef long double dou;
  6. #define pii pair<int, int>
  7.  
  8. const int maxn = 1e5+7;
  9. int num[maxn], n, q;
  10. vector<int> a[maxn];
  11. int trsz = 1;
  12. vector<int> tr(maxn*3, 0);
  13. int sz[maxn], heavy[maxn], head[maxn], par[maxn], pos[maxn], height[maxn];
  14. void dfs_sz(int u, int p) {
  15.     sz[u] = 1;
  16.     heavy[u] = 0;
  17.     for (int v : a[u]) {
  18.         if (v == p) continue;
  19.         par[v] = u;
  20.         height[v] = height[u] + 1;
  21.         dfs_sz(v, u);
  22.         sz[u] += sz[v];
  23.         if (sz[heavy[u]] < sz[v]) heavy[u] = v;
  24.     }
  25. }
  26.  
  27. int hld_timer = 0;
  28. void dfs_hld(int u, int p, int trailing_head){
  29.     pos[u] = ++hld_timer;
  30.     head[u] = trailing_head;
  31.     tr[pos[u] + trsz-1] = num[u];
  32.     if (heavy[u]){
  33.         dfs_hld(heavy[u], u, trailing_head);
  34.         for (int v : a[u]){
  35.             if (v == p || v == heavy[u]) continue;
  36.             dfs_hld(v, u, v);
  37.         }
  38.     }
  39. }
  40.  
  41. void update(int k, int x){
  42.     k = k + trsz-1;
  43.     tr[k] = x;
  44.     k /= 2;
  45.     while (k > 0) {
  46.         tr[k] = tr[k*2]^tr[k*2+1];
  47.         k /= 2;
  48.     }
  49. }
  50.  
  51. int query(int l, int r){
  52.     l = l + trsz - 1;
  53.     r = r + trsz - 1;
  54.     if (l > r) swap(l, r);
  55.     int ans = 0;
  56.     while (l <= r){
  57.         if (l % 2 == 1) ans ^= tr[l++];
  58.         if (r % 2 == 0) ans ^= tr[r--];
  59.         l /= 2; r /= 2;
  60.     }
  61.     return ans;
  62. }
  63.  
  64. int lca(int u, int v){
  65.     int ans = 0;
  66.     while (head[u] != head[v]) {
  67.         if (height[head[u]] < height[head[v]]) swap(u, v);
  68.         ans ^= query(pos[head[u]], pos[u]);
  69.         u = par[head[u]];
  70.     }
  71.     ans ^= query(pos[u], pos[v]);
  72.     return ans;
  73. }
  74.  
  75. int main() {
  76.     ios_base::sync_with_stdio(0);
  77.     cin.tie(0);
  78.     if (fopen("cowland.in", "r")){
  79.         freopen("cowland.in", "r", stdin);
  80.         freopen("cowland.out", "w", stdout);
  81.     }
  82.     cin >> n >> q;
  83.     while (trsz < n) trsz *= 2;
  84.     for (int i = 1; i <= n; i++) {
  85.         cin >> num[i];
  86.     }
  87.     for (int i = 1; i < n; i++) {
  88.         int u, v;
  89.         cin >> u >> v;
  90.         a[u].push_back(v);
  91.         a[v].push_back(u);
  92.     }
  93.     height[1] = 1;
  94.     par[1] = 0;
  95.     sz[0] = 0;
  96.     dfs_sz(1, 0);
  97.     dfs_hld(1, 0, 1);
  98.     for (int i = trsz-1; i > 0; i--) {
  99.         tr[i] = tr[i*2] ^ tr[i*2+1];
  100.     }
  101.     while (q--){
  102.         int type;
  103.         cin >> type;
  104.         if (type == 1) {
  105.             int k, x;
  106.             cin >> k >> x;
  107.             update(pos[k], x);
  108.         }
  109.         else {
  110.             int u, v;
  111.             cin >> u >> v;
  112.             cout << lca(u, v) << "\n";
  113.         }
  114.     }
  115. }
  116.  
Success #stdin #stdout 0.01s 8580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kF1D7a
language:
C++14 (gcc 8.3)
created:
2 years 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!