fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12. const int LOG = 17;  
  13.  
  14. int n, q;   
  15. int w[N];
  16. vector<int> adj[N];
  17.  
  18. struct PersistentSegTree {
  19. 	struct Node {
  20. 		int l = 0, r = 0; 
  21. 		int sum = 0;  
  22. 	}; 
  23.  
  24. 	int n; 
  25. 	vector<Node> seg; 
  26.  
  27. 	PersistentSegTree() {}
  28.  
  29. 	PersistentSegTree(int n) : n(n) {
  30. 		seg.push_back(Node());  
  31. 	}
  32.  
  33. 	int update(int pre, int l, int r, int pos) {
  34. 		int cur = seg.size(); 
  35. 		seg.push_back(seg[pre]);  
  36. 		if (l == r) {
  37. 			seg[cur].sum += 1; 
  38. 			return cur; 
  39. 		}
  40. 		int mid = (l + r) >> 1; 
  41. 		if (pos <= mid) {
  42. 			seg[cur].l = update(seg[pre].l, l, mid, pos); 
  43. 		}
  44. 		else {
  45. 			seg[cur].r = update(seg[pre].r, mid + 1, r, pos); 
  46. 		}
  47. 		int lc = seg[cur].l, rc = seg[cur].r; 
  48. 		seg[cur].sum = seg[lc].sum + seg[rc].sum; 
  49. 		return cur; 
  50. 	}
  51.  
  52. 	int getKth(int root_u, int root_v, int root_lca, int root_p_lca, int l, int r, int k) {
  53. 		if (l == r) return l; 
  54. 		int mid = (l + r) >> 1; 
  55. 		int left_u = seg[root_u].l, left_v = seg[root_v].l; 
  56. 		int left_lca = seg[root_lca].l, left_p_lca = seg[root_p_lca].l; 
  57. 		int left_sum = seg[left_u].sum + seg[left_v].sum 
  58. 					 - seg[left_lca].sum - seg[left_p_lca].sum; 
  59. 		if (k <= left_sum) {
  60. 			return getKth(left_u, left_v, left_lca, left_p_lca, l, mid, k); 
  61. 		}
  62. 		return getKth(seg[root_u].r, seg[root_v].r, seg[root_lca].r, seg[root_p_lca].r, mid + 1, r, k - left_sum);
  63. 	}
  64.  
  65. 	int update(int pre, int pos) {
  66. 		return update(pre, 0, n, pos);
  67. 	}
  68.  
  69. 	int getKth(int root_u, int root_v, int root_lca, int root_p_lca, int k) {
  70. 		return getKth(root_u, root_v, root_lca, root_p_lca, 0, n, k); 
  71. 	}
  72. };
  73.  
  74. PersistentSegTree pst;   
  75. int root[N]; 
  76.  
  77. int tin[N], tout[N], timer; 
  78. int up[LOG][N]; 
  79.  
  80. void dfs(int u, int p) {
  81. 	tin[u] = ++timer;
  82. 	root[u] = pst.update(root[p], w[u]);
  83. 	up[0][u] = p;  
  84. 	for (int i = 1; i < LOG; i++) {
  85. 		up[i][u] = up[i - 1][up[i - 1][u]]; 
  86. 	}
  87. 	for (int v : adj[u]) {
  88. 		if (v == p) continue; 
  89. 		dfs(v, u); 
  90. 	}
  91. 	tout[u] = timer; 
  92. }
  93.  
  94. bool isAncestor(int u, int v) {
  95. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
  96. }
  97.  
  98. int lca(int u, int v) {
  99. 	if (isAncestor(u, v)) return u;  
  100. 	if (isAncestor(v, u)) return v;  
  101. 	for (int i = LOG - 1; i >= 0; i--) {
  102. 		if (!isAncestor(up[i][u], v)) {
  103. 			u = up[i][u]; 
  104. 		}
  105. 	}
  106. 	return up[0][u];
  107. }
  108.  
  109. int main() {
  110. 	ios::sync_with_stdio(false); 
  111. 	cin.tie(nullptr); 	
  112. 	cin >> n >> q; 
  113. 	for (int u = 1; u <= n; u++) cin >> w[u];  
  114.  
  115. 	for (int i = 0; i < n - 1; i++) {
  116. 		int u, v;
  117. 		cin >> u >> v; 
  118. 		adj[u].push_back(v);
  119. 		adj[v].push_back(u);
  120. 	}
  121.  
  122. 	vector<int> vals;  
  123. 	for (int u = 1; u <= n; u++) vals.push_back(w[u]);
  124. 	sort(vals.begin(), vals.end());  
  125. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  126. 	int sz = vals.size();   
  127.  
  128. 	for (int u = 1; u <= n; u++) {
  129. 		w[u] = lower_bound(vals.begin(), vals.end(), w[u]) - vals.begin();
  130. 	}
  131.  
  132. 	pst = PersistentSegTree(sz - 1);
  133. 	pst.seg.reserve(18 * n);
  134. 	dfs(1, 1); 
  135.  
  136. 	while (q--) {
  137. 		int u, v, k; 
  138. 		cin >> u >> v >> k; 
  139. 		int lca_uv = lca(u, v); 
  140. 		int p_lca = (lca_uv == 1 ? 0 : up[0][lca_uv]);   
  141. 		int ans = pst.getKth(root[u], root[v], root[lca_uv], root[p_lca], k); 
  142. 		ans = vals[ans]; 
  143. 		cout << ans << '\n';
  144. 	}
  145. }
Success #stdin #stdout 0.01s 13836KB
comments (?)
stdin
copy 
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2
stdout
copy 
2
8
9
105
7
https://ideone.com/wPvKRd
language:
C++14 (gcc 8.3)
created:
12 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!