fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define rep(i, l, r) for(int i = l; i <= r; i++)
  3. #define rep2(i, l, r) for(int i = l; i >= r; i--)
  4. #define fi first
  5. #define se second
  6. #define bit(i, x) (x >> i & 1)
  7. const int N = 3e5 + 3;
  8. using namespace std;
  9. int n, m, a[N];
  10. vector<int> G[N];
  11. int parr[N];
  12. int sz[N], big[N], depth[N];
  13. int in[N], top[N], cnt;
  14. struct node{
  15.     node *child[2];
  16.     int num;
  17.     node() {
  18.         child[0] = child[1] = nullptr;
  19.         num = 0;
  20.     }
  21. };
  22. void add(int u, node *cur) {
  23.     assert(cur != nullptr);
  24.     rep2(i, 16, 0) {
  25.         int x = bit(i, u);
  26.         if (cur -> child[x] != nullptr) {
  27.             node *old = cur -> child[x];
  28.             cur -> child[x] = new node;
  29.             cur = cur -> child[x];
  30.             cur -> child[0] = old -> child[0];
  31.             cur -> child[1] = old -> child[1];
  32.             cur -> num = old -> num + 1;
  33.         }
  34.         else {
  35.             cur -> child[x] = new node;
  36.             cur = cur -> child[x];
  37.             cur -> num++;
  38.         }
  39.     }
  40. }
  41. bool check(int u, node *cur) {
  42.     assert(cur != nullptr);
  43.     rep2(i, 16, 0) {
  44.         int x = bit(i, u);
  45.         if (cur -> child[x] == nullptr) return 0;
  46.         cur = cur -> child[x];
  47.     }
  48.     return 1;
  49. }
  50. void dfs(int u, int par, vector<node*> &root) {
  51.     root[u] = new node;
  52.     root[u] -> child[0] = root[par] -> child[0];
  53.     root[u] -> child[1] = root[par] -> child[1];
  54.     root[u] -> num = root[par] -> num;
  55.     add(a[u], root[u]);
  56.     parr[u] = par;
  57.  
  58.     sz[u] = 1, big[u] = 0;
  59.     for(int v : G[u]) if (v != par) {
  60.         depth[v] = depth[u] + 1;
  61.         dfs(v, u, root);
  62.         sz[u] += sz[v];
  63.         if (sz[big[u]] < sz[v]) big[u] = v;
  64.     }
  65. }
  66. void rebuild(int u, int topp) {
  67.     in[u] = ++cnt;
  68.     top[u] = topp;
  69.     if (big[u]) rebuild(big[u], topp);
  70.     for(int v : G[u]) if (v != parr[u] && v != big[u]) {
  71.         rebuild(v, v);
  72.     }
  73. }
  74. int lca(int x, int y) {
  75.     while (top[x] != top[y]) {
  76.         if (depth[top[x]] < depth[top[y]]) swap(x, y);
  77.         x = parr[top[x]];
  78.     }
  79.     if (depth[x] > depth[y]) swap(x, y);
  80.     return x;
  81. }
  82. int get(node *cur, int x) {
  83.     if (cur == nullptr) return 0;
  84.     if (cur -> child[x] == nullptr) return 0;
  85.     return cur -> child[x] -> num;
  86. }
  87. void ask(node *x, node *y, node *p, node *pp, int val) {
  88.     int res = 0;
  89.     assert(x != nullptr);
  90.     assert(y != nullptr);
  91.     assert(p != nullptr);
  92.     assert(pp != nullptr);
  93.     rep2(i, 16, 0) {
  94.         int s[2];
  95.         s[0] = get(x, 0) + get(y, 0) - get(p, 0) - get(pp, 0);
  96.         s[1] = get(x, 1) + get(y, 1) - get(p, 1) - get(pp, 1);
  97.         int v = bit(i, val);
  98.         if (s[v ^ 1] > 0) {
  99.             res |= (1 << i);
  100.             if (x != nullptr) x = x -> child[v ^ 1];
  101.             if (y != nullptr) y = y -> child[v ^ 1];
  102.             if (p != nullptr) p = p -> child[v ^ 1];
  103.             if (pp != nullptr) pp = pp -> child[v ^ 1];
  104.         }
  105.         else {
  106.             if (x != nullptr) x = x -> child[v];
  107.             if (y != nullptr) y = y -> child[v];
  108.             if (p != nullptr) p = p -> child[v];
  109.             if (pp != nullptr) pp = pp -> child[v];
  110.         }
  111.     }
  112.     cout << res << "\n";
  113. }
  114. void inp() {
  115. //    cin >> n >> m;
  116.     rep(i, 1, n) cin >> a[i];
  117.     rep(i, 1, n - 1) {
  118.         int x, y; cin >> x >> y;
  119.         G[x].push_back(y);
  120.         G[y].push_back(x);
  121.     }
  122. }
  123. void solve() {
  124.     vector<node*> root(n + 3);
  125.     root[0] = new node;
  126.     dfs(1, 0, root);
  127.     rebuild(1, 1);
  128.     rep(i, 1, m) {
  129.         int x, y, z; cin >> x >> y >> z;
  130.         int p = lca(x, y);
  131.         ask(root[x], root[y], root[p], root[parr[p]], z);
  132.     }
  133.     rep(i, 1, n) G[i].clear();
  134.     cnt = 0;
  135. }
  136. node *root[N];
  137. int main()
  138. {
  139.     ios_base::sync_with_stdio(0);
  140.     cin.tie(0); cout.tie(0);
  141.  
  142.     #define task "bus"
  143. //    freopen(task".inp", "r", stdin);
  144. //    freopen(task".out", "w", stdout);
  145.  
  146. //    freopen("testing.txt", "r", stdin);
  147.  
  148.     while (cin >> n >> m) {
  149.         inp();
  150.         solve();
  151.     }
  152.  
  153. //    root[0] = new node;
  154. //
  155. //    root[1] = new node;
  156. //    root[1] -> child[0] = root[0] -> child[0];
  157. //    root[1] -> child[1] = root[0] -> child[1];
  158. //    root[1] -> num = root[0] -> num;
  159. //
  160. //    add(2, root[1]);
  161. //    root[2] = new node;
  162. //    root[2] -> child[0] = root[1] -> child[0];
  163. //    root[2] -> child[1] = root[1] -> child[1];
  164. //    root[2] -> num = root[1] -> num;
  165. //
  166. //    add(3, root[2]);
  167. //
  168. //    cout << check(3, root[1]);
  169.  
  170.     return 0 ^ 0;
  171. }
  172. // Identify Thief O_O
  173.  
Success #stdin #stdout 0.01s 11820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jWOuw7
language:
C++ (gcc 8.3)
created:
364 days 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!