Advertisement
Guest User

Untitled

a guest
Jul 24th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int n, q;
  9. int x[3];
  10. int a[400000];
  11. int d[400000];
  12. int p[400000];
  13. pair<int, int> tree[400000];
  14. vector<int> g[400000];
  15. vector<int> v;
  16.  
  17. pair<int, int> mp(pair<int, int> lhs, pair<int, int> rhs)
  18. {
  19. if (lhs.first < rhs.first)
  20. return lhs;
  21. return rhs;
  22. }
  23.  
  24. void dfs(int curr, int prev, int dpt)
  25. {
  26. v.push_back(dpt);
  27. a[curr] = v.size() - 1;
  28. d[curr] = dpt;
  29. p[v.size() - 1] = curr;
  30.  
  31. for (int i = 0; i < g[curr].size(); i++)
  32. {
  33. if (g[curr][i] == prev) continue;
  34.  
  35. dfs(g[curr][i], curr, dpt + 1);
  36. v.push_back(dpt);
  37. a[curr] = v.size() - 1;
  38. d[curr] = dpt;
  39. p[v.size() - 1] = curr;
  40. }
  41. }
  42.  
  43. void build(int node, int s, int e)
  44. {
  45. if (s > e)
  46. return;
  47.  
  48. if (s == e)
  49. {
  50. tree[node] = make_pair(v[s], s);
  51. return;
  52. }
  53.  
  54. int mid = (s + e) / 2;
  55.  
  56. build(2 * node, s, mid);
  57. build(2 * node + 1, mid + 1, e);
  58.  
  59. tree[node] = mp(tree[2 * node], tree[2 * node + 1]);
  60. }
  61.  
  62. pair<int, int> query(int node, int s, int e, int l, int r)
  63. {
  64. if (s > r || l > e || s > e)
  65. return make_pair(1 << 30, l);
  66.  
  67. // cout << s << " " << e << " " << l << " " << r << endl;
  68.  
  69. if (s >= l && e <= r)
  70. return tree[node];
  71.  
  72. int mid = (s + e) / 2;
  73.  
  74. pair<int, int> s1 = query(2 * node, s, mid, l, r);
  75. pair<int, int> s2 = query(2 * node + 1, mid + 1, e, l, r);
  76.  
  77. // cout << s << " " << e << " " << l << " " << r << ": " << s1.first << " " << s1.second << "; " << s2.first << " " << s2.second << endl;
  78.  
  79. return mp(s1, s2);
  80. }
  81.  
  82. int dst(int ca, int cb)
  83. {
  84. int can = p[query(1, 0, n - 1, min(a[ca], a[cb]), max(a[ca], a[cb])).second];
  85.  
  86. cout << ca + 1 << " -> " << cb + 1 << " " << can + 1 << ": " << d[ca] << " - " << d[can] << " + " << d[cb] << " = " << d[ca] - d[can] + d[cb] << endl;
  87.  
  88. return d[ca] - d[can] + d[cb];
  89. }
  90.  
  91. int main()
  92. {
  93. ifstream cin("in.txt");
  94.  
  95. cin >> n >> q;
  96.  
  97. int curr;
  98. for (int i = 1; i < n; i++)
  99. {
  100. cin >> curr;
  101.  
  102. g[i].push_back(curr - 1);
  103. g[curr - 1].push_back(i);
  104. }
  105.  
  106. dfs(0, -1, 0);
  107. build(1, 0, v.size() - 1);
  108.  
  109. // for (int i = 0; i < v.size(); i++)
  110. // cout << p[i] + 1 << " ";
  111. // cout << endl;
  112. // for (int i = 0; i < v.size(); i++)
  113. // cout << v[i] << " ";
  114. // cout << "\n\n";
  115.  
  116. int ac, bc, ab, cres, res;
  117. for (int i = 0; i < q; i++)
  118. {
  119. for (int j = 0; j < 3; j++)
  120. {
  121. cin >> x[j];
  122. x[j]--;
  123. }
  124.  
  125. // sort(x, x + 3);
  126.  
  127. res = 0;
  128. // do
  129. // {
  130. ac = p[query(1, 0, v.size() - 1, min(a[x[0]], a[x[2]]), max(a[x[0]], a[x[2]])).second];
  131. bc = p[query(1, 0, v.size() - 1, min(a[x[1]], a[x[2]]), max(a[x[1]], a[x[2]])).second];
  132. ab = p[query(1, 0, v.size() - 1, min(a[x[0]], a[x[1]]), max(a[x[0]], a[x[1]])).second];
  133.  
  134. cout << ac + 1 << " " << bc + 1 << " " << ab + 1 << endl;
  135.  
  136. cres = 0;
  137. if (ac == bc)
  138. cres += dst(ab, ac);
  139.  
  140. cres += dst((d[ac] > d[bc] ? ac : bc), x[2]);
  141. res = max(cres, res);
  142. // }
  143. // while (next_permutation(x, x + 3));
  144.  
  145. cout << res + 1 << endl;
  146. }
  147.  
  148. return 0;
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement