fork download
copy 
  1. // O(n*log(n)*log(MAX) + q*log(MAX))
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8. typedef long double ld;
  9.  
  10. const int maxn = 200005;
  11. const int lgn = 18;
  12. const int depth = 20;
  13.  
  14. struct Node{
  15.     int l, r, id;
  16. };
  17.  
  18. Node trie[maxn*lgn*depth];
  19. vector<int> g[maxn];
  20. int sz[maxn], root[maxn], val[maxn], st[maxn], en[maxn], vert[2*maxn];
  21. int ptr, tptr;
  22.  
  23. void dfs(int v, int p){
  24.     sz[v] = 1;
  25.     vert[tptr] = v;
  26.     st[v] = tptr++;
  27.     for(auto u : g[v]){
  28.         if(u != p){
  29.             dfs(u, v);
  30.             sz[v] += sz[u];
  31.         }
  32.     }
  33.     vert[tptr] = v;
  34.     en[v] = tptr++;
  35. }
  36.  
  37. void clear(int v){
  38.     trie[v].l = trie[v].r = trie[v].id = 0;
  39. }
  40.  
  41. int update(int v, int k, int id){
  42. 	clear(ptr);
  43. 	int nv = ptr++;
  44. 	trie[nv] = trie[v];
  45. 	int ret = nv;
  46. 	for(int i = depth - 1; i >= 0; i--){
  47. 		clear(ptr);
  48. 		if((k>>i)&1){
  49. 			trie[nv].r = ptr++;
  50. 			trie[trie[nv].r] = trie[trie[v].r];
  51. 			nv = trie[nv].r;
  52. 			v = trie[v].r;
  53. 		}else{
  54. 			trie[nv].l = ptr++;
  55. 			trie[trie[nv].l] = trie[trie[v].l];
  56. 			nv = trie[nv].l;
  57. 			v = trie[v].l;
  58. 		}
  59. 	}
  60. 	if(!trie[nv].id)trie[nv].id = id;
  61. 	else trie[nv].id = min(trie[nv].id, id);
  62. 	return ret;
  63. }
  64.  
  65. int query(int v, int k){
  66.     for(int i = depth - 1; i >= 0; i--){
  67.         if((k>>i)&1){
  68.             if(trie[v].l)v = trie[v].l;
  69.             else v = trie[v].r;
  70.         }else{
  71.             if(trie[v].r)v = trie[v].r;
  72.             else v = trie[v].l;
  73.         }
  74.     }
  75.     return trie[v].id;
  76. }
  77.  
  78. void createRoot(int v, int p){
  79.     int bg = -1;
  80.     for(auto u : g[v]){
  81.         if(u != p && (bg == -1 || sz[bg] < sz[u]))bg = u;
  82.     }
  83.     for(auto u : g[v]){
  84.         if(u != p)createRoot(u, v);
  85.     }
  86.     root[v] = (bg == -1)?0:root[bg];
  87.     root[v] = update(root[v], val[v], v);
  88.     for(auto u : g[v]){
  89.         if(u == p || u == bg)continue;
  90.         for(int i = st[u]; i < en[u]; i++){
  91.             int w = vert[i];
  92.             if(st[w] == i){
  93.                 root[v] = update(root[v], val[w], w);
  94.             }
  95.         }
  96.     }
  97. }
  98.  
  99. void solve(){
  100.     int n, q, u, v, k;
  101.     cin>>n>>q;
  102.     for(int i = 1; i <= n; i++){
  103.         cin>>val[i];
  104.         g[i].clear();
  105.     }
  106.     for(int i = 1; i < n; i++){
  107.         cin>>u>>v;
  108.         g[u].push_back(v);
  109.         g[v].push_back(u);
  110.     }
  111.     dfs(1, -1);
  112.     ptr = tptr = 1;
  113.     trie[0].l = trie[0].r = trie[0].id = 0;
  114.     createRoot(1, -1);
  115.     int last_answer = 0, last_node = 0;
  116.     while(q--){
  117.         cin>>v>>k;
  118.         v ^= last_node;
  119.         k ^= last_answer;
  120.         last_node = query(root[v], k);
  121.         last_answer = val[last_node]^k;
  122.         cout<<last_node<<" "<<last_answer<<'\n';
  123.     }
  124. }
  125.  
  126. int main(){
  127.  
  128. 	ios::sync_with_stdio(false);
  129. 	cin.tie(NULL);
  130. 	cout.tie(NULL);
  131.  
  132.     int t;
  133.     cin>>t;
  134.     while(t--)solve();
  135. }
Success #stdin #stdout 0s 869376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Vpy9NJ
language:
C++14 (gcc 8.3)
created:
6 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!