fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long in;
  4. #define lcm(a,b) ((a*b)/__gcd(a,b))
  5. #define max(a,b) ((a)>(b)?(a):(b))
  6. #define vi vector<in>
  7. #define vvi vector<vector<in> >
  8. #define vpi vector<pair<in,in> >
  9. #define pb push_back
  10. #define mp make_pair
  11. #define pii pair<in,in>
  12. #define fi first
  13. #define se second
  14. #define lb lower_bound
  15. #define ub upper_bound
  16. #define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  17.  
  18. const in maxn=200005;
  19. vector<in> adj[maxn];
  20. vector<in> val(maxn);
  21. vector<in> ar;
  22. vector<pii> tme(maxn,mp(0,0));
  23. vector<in> flag(maxn);
  24. struct trie
  25. {
  26. trie* arr[2];
  27. in minver,mst;//minimumVertex,maxStartTime
  28. trie() {
  29. arr[0]=arr[1]=NULL;
  30. minver=maxn;
  31. mst=0;
  32. }
  33. };
  34. vector<trie*> ptries(2*maxn);
  35.  
  36. //persistent trie
  37. trie* insert(trie* root,in ver)
  38. {
  39. trie* newroot=new trie();
  40. trie* source=newroot;
  41. in v=val[ver];
  42. in st=tme[ver].fi;
  43. trie* temp=root;
  44. for(in i=19; i>=0; i--)
  45. {
  46. bool bit=v&(1<<i);
  47. newroot->mst=max(newroot->mst,st);
  48. if(temp!=NULL)
  49. {
  50. newroot->arr[!bit]=temp->arr[!bit];
  51. temp=temp->arr[bit];
  52. }
  53. newroot->arr[bit]=new trie();
  54. newroot=newroot->arr[bit];
  55. }
  56. newroot->mst=max(newroot->mst,st);
  57. newroot->minver=min(newroot->minver,ver);
  58. return source;
  59. }
  60. //euler tour
  61. void dfs(in i,in p)
  62. {
  63. ar.pb(i);
  64. for(in j:adj[i])
  65. if(j!=p)
  66. dfs(j,i);
  67. ar.pb(i);
  68. }
  69.  
  70. pii querytrie(in ver,in k)
  71. {
  72. trie* root=ptries[tme[ver].se];
  73. in ans=0,v=k;
  74. trie* temp=root;
  75. for(in i=19; i>=0; i--)
  76. {
  77. bool bit=v&(1<<i);
  78. if(temp->arr[!bit]!=NULL && (temp->arr[!bit]->mst)>=tme[ver].fi)//opposite bit there and maxStartTime >=startTime of ver
  79. {
  80. ans=ans|(1<<i);
  81. temp=temp->arr[!bit];
  82. }
  83. else
  84. temp=temp->arr[bit];
  85. }
  86. return {temp->minver,ans};
  87. }
  88.  
  89. int main() {
  90. // your code goes here
  91. in t;
  92. cin>>t;
  93. while(t--)
  94. {
  95. ar.clear();
  96. ptries.clear();
  97. val.clear();
  98. for(in i=0; i<maxn; i++)
  99. {
  100. adj[i].clear();
  101. tme[i]=mp(0,0);
  102. flag[i]=0;
  103. }
  104. in n,q;
  105. cin>>n>>q;
  106. for(in i=1; i<=n; i++)
  107. cin>>val[i];
  108. for(in i=1; i<n; i++)
  109. {
  110. in a,b;
  111. cin>>a>>b;
  112. adj[a].pb(b);
  113. adj[b].pb(a);
  114. }
  115. dfs(1,0);
  116. for (int i = 0; i < 2*n; i++) {
  117. if (tme[ar[i]].fi == 0)
  118. tme[ar[i]].fi = i+1;
  119. else
  120. tme[ar[i]].se = i+1;
  121. }
  122. ptries[1]=insert(new trie(),ar[0]);
  123. in j=0;
  124. for(in i=1; i<2*n; i++)
  125. {
  126. if(flag[ar[i]])
  127. {
  128. ptries[i+1]=ptries[i];
  129. }
  130. else
  131. {
  132. flag[ar[i]]=1;
  133. ptries[i+1]=insert(ptries[i],ar[i]);
  134. }
  135.  
  136. }
  137. in xl=0,vl=0;
  138. for(in i=1; i<=q; i++)
  139. {
  140. in a,b;
  141. cin>>a>>b;
  142. in v=a^vl,k=b^xl;
  143. auto pp=querytrie(v,k);
  144. cout<<pp .fi<<" "<<pp.se<<endl;
  145. xl=pp.se;
  146. vl=pp.fi;
  147. }
  148. }
  149. return 0;
  150. }
Runtime error #stdin #stdout 0s 29312KB
stdin
Standard input is empty
stdout
Standard output is empty