fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty