Advertisement
Guest User

Untitled

a guest
May 22nd, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.80 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <fstream>
  3. #include <ctime>
  4. #include <vector>
  5. #include <string>
  6.  
  7. using namespace std;
  8. int n = 0;
  9. int MIN = 2 * 100001;
  10. vector<bool> used;
  11. long long time_cur = 0;
  12. struct node {
  13. vector<node*> parents;
  14. vector<node*> childs;
  15. int timein = 0;
  16. int timeout = 0;
  17. int num = 0;
  18. int weight = -1;
  19. };
  20. void dfs(node* cur, int mpot) {
  21. used[cur->num] = true;
  22. time_cur++;
  23. cur->timein = time_cur;
  24. for (int i = 1; i <= mpot; i++) {
  25. if (cur->parents[i - 1] != nullptr) {
  26. cur->parents[i] = (cur->parents[i - 1]->parents[i - 1]);
  27. }
  28. }
  29. for (auto child : cur->childs) {
  30. if (child != cur) {
  31. dfs(child, mpot);
  32. }
  33. }
  34. time_cur++;
  35. cur->timeout = time_cur;
  36. }
  37. node* lca(node* first, node* second) {
  38. if (first->timein <= second->timein && first->timeout >= second->timeout) {
  39. return first;
  40. }
  41. else if (second->timein <= first->timein && second->timeout >= first->timeout) {
  42. return second;
  43. }
  44. for (int i = first->parents.size() - 1; i >= 0; i--) {
  45. if (first->parents[i] == nullptr) {
  46. first->parents[i] = first;
  47. }
  48. if (second->parents[i] == nullptr) {
  49. second->parents[i] = second;
  50. }
  51. if (first->parents[i]->timein >= second->timein || first->parents[i]->timeout <= second->timeout) {
  52. first = first->parents[i];
  53. }
  54. }
  55. first = first->parents[0];
  56. return first;
  57.  
  58. }
  59. int min_pot(int x) {
  60. int a = 0;
  61. while ((1 << a) <= x) {
  62. a++;
  63. }
  64. return a;
  65. }
  66. int main() {
  67. scanf("%d", &n);
  68. vector<node*> nodes(n);
  69. for (int i = 0; i < n; i++) {
  70. nodes[i] = new node;
  71. nodes[i]->num = i;
  72. }
  73. for (int i = 1; i < n; i++) {
  74. int p = 0, y = 0;
  75. scanf("%d %d", &p, &y);
  76. nodes[i]->parents.push_back(nodes[p - 1]);
  77. nodes[p - 1]->childs.push_back(nodes[i]);
  78. nodes[i]->weight = y;
  79. }
  80. int mpot = min_pot(n);
  81. mpot++;
  82. for (int i = 0; i < n; ++i) {
  83. nodes[i]->parents.resize(mpot);
  84. }
  85. used.resize(n, false);
  86. for (int i = 0; i < n; i++) {
  87. if (!used[i])
  88. dfs(nodes[i], mpot - 1);
  89. }
  90.  
  91. int MIN = 2 * 100001;
  92. int m = 0;
  93. scanf("%d", &m);
  94. for (int i = 0; i < m; i++) {
  95. int a, b;
  96. scanf("%d %d", &a, &b);
  97. node *a1 = nodes[a - 1];
  98. node *b1 = nodes[b - 1];
  99. node *ver = lca(a1, b1);
  100.  
  101. for (int i = a1->parents.size() - 1; i >= 0; i--) {
  102. if (a1->weight < MIN && a1->weight != -1) {
  103. MIN = a1->weight;
  104. }
  105. if (a1->parents[i] != nullptr) {
  106. a1->parents[i] = a1;
  107. }
  108. if (a1->weight < MIN && a1->weight != -1) {
  109. MIN = a1->weight;
  110. }
  111. }
  112. for (int i = b1->parents.size() - 1; i >= 0; i--) {
  113. if (b1->weight < MIN && b1->weight != -1) {
  114. MIN = b1->weight;
  115. }
  116. if (b1->parents[i] != nullptr) {
  117. b1->parents[i] = b1;
  118. }
  119. if (b1->weight < MIN && b1->weight != -1) {
  120. MIN = b1->weight;
  121. }
  122. }
  123. }
  124.  
  125. printf("%d\n", MIN);
  126.  
  127. system("pause");
  128. return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement