fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define all(x) begin(x), end(x)
  6.  
  7. const int maxn = 2e5 + 42, logn = 20, maxm = 1 << 20;
  8. const int maxs = 2 * maxn * logn * logn;
  9.  
  10. int L[maxs], R[maxs], mn[maxs];
  11. int rt[maxn];
  12. int sz = 1;
  13.  
  14. int copy(int v = 0) {
  15. 	L[sz] = L[v];
  16. 	R[sz] = R[v];
  17. 	mn[sz] = mn[v];
  18. 	return sz++;
  19. }
  20.  
  21. void upd(int p, int c, int v, int l = 0, int r = maxm) {
  22. 	mn[v] = min(mn[v], c);
  23. 	if(r - l > 1) {
  24. 		int m = (l + r) / 2;
  25. 		if(p < m) {
  26. 			upd(p, c, L[v] = copy(L[v]), l, m);
  27. 		} else {
  28. 			upd(p, c, R[v] = copy(R[v]), m, r);
  29. 		}
  30. 	}
  31. }
  32. pair<int, int> get(int k, int v, int l = 0, int r = maxm) {
  33. 	if(r - l == 1) {
  34. 		return {mn[v], l};
  35. 	} else {
  36. 		int m = (l + r) / 2;
  37. 		if(((k ^ (m - l)) < k && L[v]) || !R[v]) {
  38. 			return get(k, L[v], l, m);
  39. 		} else {
  40. 			return get(k, R[v], m, r);
  41. 		}
  42. 	}
  43. }
  44.  
  45. int w[maxn];
  46. vector<int> g[maxn];
  47. set<int> sub[maxn];
  48. void dfs(int v = 1, int p = 1) {
  49. 	rt[v] = copy();
  50. 	sub[v] = {v};
  51. 	upd(w[v], v, rt[v]);
  52. 	for(auto u: g[v]) {
  53. 		if(u != p) {
  54. 			dfs(u, v);
  55. 			if(sub[v].size() < sub[u].size()) {
  56. 				rt[v] = copy(rt[u]);
  57. 				swap(sub[v], sub[u]);
  58. 			}
  59. 			for(auto it: sub[u]) {
  60. 				sub[v].insert(it);
  61. 				upd(w[it], it, rt[v]);
  62. 			}
  63. 		}
  64. 	}
  65. }
  66.  
  67. void solve() {
  68. 	int n, q;
  69. 	cin >> n >> q;
  70. 	for(int i = 1; i <= n; i++) {
  71. 		cin >> w[i];
  72. 	}
  73. 	for(int i = 2; i <= n; i++) {
  74. 		int x, y;
  75. 		cin >> x >> y;
  76. 		g[x].push_back(y);
  77. 		g[y].push_back(x);
  78. 	}
  79. 	dfs();
  80. 	int x = 0, y = 0;
  81. 	while(q--) {
  82. 		int k, v;
  83. 		cin >> v >> k;
  84. 		v ^= x, k ^= y;
  85. 		tie(x, y) = get(k, rt[v]);
  86. 		y ^= k;
  87. 		cout << x << ' ' << y << "\n";
  88. 	}
  89. 	for(int i = 1; i <= n; i++) {
  90. 		g[i].clear();
  91. 		sub[i].clear();
  92. 	}
  93. 	for(int i = 0; i < sz; i++) {
  94. 		L[i] = R[i] = 0;
  95. 		mn[i] = maxm;
  96. 	}
  97. 	sz = 1;
  98. }
  99.  
  100. signed main() {
  101. 	//freopen("input.txt", "r", stdin);
  102. 	//freopen("output.txt", "w", stdout);
  103. 	ios::sync_with_stdio(0);
  104. 	cin.tie(0);
  105. 	fill(mn, mn + maxs, maxm);
  106. 	int t;
  107. 	cin >> t;
  108. 	while(t--) {
  109. 		solve();
  110. 	}
  111. 	return 0;
  112. }
  113.  
Success #stdin #stdout 0.14s 1906176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0uefPJ
language:
C++14 (gcc 8.3)
created:
5 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!