fork download
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define pb(x) push_back(x)
  5. #define mp(a, b) make_pair(a, b)
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef vector<ll> vll;
  10. typedef vector<int> vi;
  11. typedef pair<ll, ll> pll;
  12. const int MOD = 1e9 + 7;
  13. const int LOG = 20;
  14. vector< vi > adj;
  15. vi level;
  16. vi parent;
  17. vector<bool> visited;
  18. vector< vi > up;
  19. vector< vi > lca_right;
  20. vector< vi > lca_left;
  21. int n;
  22. void bfs(int src) {
  23. queue<int> q;
  24. q.push(src);
  25. while(!q.empty()) {
  26. int u = q.front();
  27. visited[u] = true;
  28. q.pop();
  29. for(auto v: adj[u]) {
  30. if(!visited[v]) {
  31. level[v] = level[u] + 1;
  32. parent[v] = u;
  33. up[v][0] = u;
  34. q.push(v);
  35. }
  36. }
  37. }
  38. }
  39. void fill_up() {
  40. for(int i = 1; i < LOG; ++i)
  41. for(int j = 0; j < n; ++j)
  42. if(up[j][i - 1] != -1)
  43. up[j][i] = up[up[j][i - 1]][i - 1];
  44. }
  45. int walk(int u, int k) {
  46. int node = u;
  47. int ct = 0;
  48. while(k) {
  49. if(k % 2)
  50. node = up[node][ct];
  51. ct++;
  52. if(ct > LOG)
  53. return -1;
  54. k /= 2;
  55. }
  56. return node;
  57. }
  58. int lca(int u, int v) {
  59. if(level[u] > level[v])
  60. swap(u, v);
  61. int diff = abs(level[u] - level[v]);
  62. v = walk(v, diff);
  63. if(u == v)
  64. return u;
  65. while(1) {
  66. int jump = 0;
  67. for(int k = 0; k < LOG; ++k) {
  68. if(up[u][k] == up[v][k])
  69. break;
  70. jump = k;
  71. }
  72. u = up[u][jump];
  73. v = up[v][jump];
  74. if(u == v)
  75. return u;
  76. }
  77. }
  78. vll two(LOG + 1, 1);
  79. void fill_up_sparse() {
  80. for(int i = 0; i < n; ++i) {
  81. lca_right[i][0] = i;
  82. lca_left[i][0] = i;
  83. }
  84.  
  85. for(int i = 1; i <= LOG; ++i)
  86. two[i] = two[i - 1] * 2ll;
  87.  
  88. for(int i = 1; i < LOG; ++i) {
  89. for(int j = 0; j < n; ++j) {
  90. if(lca_right[j][i - 1] != -1 and ((j + two[i - 1]) < n) and (lca_right[j + two[i - 1]][i - 1] != -1))
  91. lca_right[j][i] = lca(lca_right[j][i - 1], lca_right[j + two[i - 1]][i - 1]);
  92. }
  93. }
  94.  
  95. for(int i = 1; i < LOG; ++i)
  96. for(int j = n - 1; j >= 0; j--)
  97. if(lca_left[j][i - 1] != -1 and (j - two[i - 1]) >= 0 and lca_left[j - two[i - 1]][i -1] != -1)
  98. lca_left[j][i] = lca(lca_left[j][i - 1], lca_left[j - two[i - 1]][i -1]);
  99. }
  100. int lca_range(int l, int r) {
  101. int len = 0;
  102. for(int i = 0; i < LOG; ++i) {
  103. if(l + two[i] > r)
  104. break;
  105. len = i;
  106. }
  107. // if(l == 0 and r == 8)
  108. // cout << "***" << len << " " << lca_right[l][len] << " " << lca_left[r][len] << endl;
  109. return lca(lca_right[l][len], lca_left[r][len]);
  110. }
  111. int main() {
  112. std :: ios_base :: sync_with_stdio(false);
  113. cin.tie(NULL), cout.tie(NULL);
  114. cin >> n;
  115. adj.assign(n, vi());
  116. level.assign(n, 0);
  117. parent.assign(n, -1);
  118. visited.assign(n, false);
  119. up.assign(n, vi(LOG, -1));
  120. lca_left.assign(n, vi(LOG, -1));
  121. lca_right.assign(n, vi(LOG, -1));
  122. int q;
  123. cin >> q;
  124. int x, y;
  125. for(int i = 2; i <= n; ++i) {
  126. cin >> x;
  127. y = i;
  128. x--, y--;
  129. adj[x].pb(y);
  130. adj[y].pb(x);
  131. }
  132. bfs(0);
  133. fill_up();
  134. fill_up_sparse();
  135. int l, r;
  136. while(q--) {
  137. cin >> l >> r;
  138. l--, r--;
  139. int low = l;
  140. int high = r;
  141. int lca_LR = lca_range(l, r);
  142. int left = -1;
  143. int right = -1;
  144. while(low < high) {
  145. int mid = low + (high - low + 1) / 2;
  146. if(lca_range(l, mid) == lca_LR)
  147. high = mid - 1;
  148. else
  149. low = mid;
  150. }
  151. if(lca_range(l, low) != lca_LR)
  152. left = low;
  153. if(left != -1 and left == r - 1) {
  154. cout << r + 1 << " " << level[lca_range(l, left)] << endl;
  155. continue;
  156. }
  157. low = l;
  158. high = r;
  159. while(low < high) {
  160. int mid = low + (high - low) / 2;
  161. if(lca_range(mid, r) == lca_LR)
  162. low = mid + 1;
  163. else
  164. high = mid;
  165. }
  166. if(lca_range(low, r) != lca_LR)
  167. right = low;
  168. if(right != -1 and right == l + 1) {
  169. cout << l + 1 << " " << level[lca_range(right, r)] << endl;
  170. continue;
  171. }
  172. if(left + 1 == right - 1) {
  173. cout << left + 2 << " " << level[lca(lca_range(l, left), lca_range(right, r))] << endl;
  174. continue;
  175. }
  176. cout << l + 1 << " " << level[lca_LR] << endl;
  177. }
  178. return 0;
  179. }
  180.  
Runtime error #stdin #stdout 0s 15248KB
stdin
Standard input is empty
stdout
Standard output is empty