Advertisement
ke_timofeeva7

Untitled

Feb 5th, 2023
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.25 KB | None | 0 0
  1. /*
  2. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣠⡯⠀⠀⠀⢠⡐⠀⠀⠀⠀⠀
  3. ⠀⠀⠀⢀⣤⠔⠂⠀⠀⠀⢤⣤⣤⣤⣄⣀⣀⣀⣀⡀⠀⢀⣀⣀⣀⡀⠀⠀⠀⢀⢀⣀⣠⣤⣴⣶⣾⠉⠉⠙⣶⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⣰⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀
  4. ⠀⠀⠰⣿⣷⣾⣿⣷⣴⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠉⠛⢿⣿⣿⣿⣿⣿⣿⣿⠿⠿⣿⣶⣿⣿⣿⣿⣤⣂⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣤⣤⣤⣴⣦⣾⣿⣿⣿⣶⣦⣴⣶⣶⠀
  5. ⠀⠀⠀⣿⣿⣿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣤⣶⣶⣿⣿⣿⣿⣿⣿⣿⣯⣤⣤⣿⡿⠿⠿⠿⠛⠛⠛⠛⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣽⣿⣿⡟⢻⣿⣿⣿⡟⣿⣿⣿⣿⠉⠉⠁⠀
  6. ⠀⠀⠀⣹⣟⣿⣦⠈⠻⠋⢉⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣿⣠⣾⣿⣿⣏⣤⣾⣿⣿⣿⡆⠀
  7. ⠀⠀⢀⣿⣿⣿⣿⣦⠀⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⢿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡧⠀
  8. ⠀⠀⢸⣿⣿⣿⣿⣿⡀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡈⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⡄⠀
  9. ⠀⠀⠈⠿⠿⠁⣿⣿⣿⠎⠻⣯⠉⠉⠉⠈⠉⠉⠉⠉⠉⠉⠉⠉⠉⠉⢹⣿⢻⠉⠉⠁⠈⠻⢦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠁⠉⠙⠛⠛⢿⣿⠟⠋⠁⠀⠀⠀⠈⠀
  10. ⠀⠀⠀⠀⠀⠀⢹⣿⡟⠀⠀⠈⠳⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⠞⠀⠀⠀⠀⠀⠀⠙⠳⠤⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠁⠀⠀⠀⠀⠀⠸⣿⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⠀
  11. ⠀⠀⠀⠀⠀⠀⢈⡟⠇⠀⠀⠀⠀⠈⠁⠤⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  12. ⠀⠀⠀⠀⠀⠀⠀⠙⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⠂⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡘⡀⠀
  13. ⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  14. */
  15. #include <iostream>
  16. #include <string>
  17. #include <sstream>
  18. #include <cmath>
  19. #include <memory.h>
  20. #include <algorithm>
  21. #include <stack>
  22. #include <deque>
  23. #include <iomanip>
  24. #include <stdio.h>
  25. #include <queue>
  26. #include <map>
  27. #include <set>
  28. #include <unordered_map>
  29. #include <unordered_set>
  30. #include <random>
  31. #include <ctime>
  32. #include <cstdlib>
  33. #include <cassert>
  34. #include <iterator>
  35. #include <chrono>
  36. #include <array>
  37. #include <bitset>
  38. #define int long long
  39. #define itn long long
  40. #define fro for
  41. #define intt __int128
  42. #define pii pair <int, int>
  43. #define debug(x) cerr << (#x) << " " << (x) << endl
  44. #define pb push_back
  45. #define all(vc) vc.begin(), vc.end()
  46. #define fir first
  47. #define sec second
  48. #define endl "\n"
  49. #define un unsigned
  50. #define INF 1000000010
  51. #define double long double
  52. using namespace std;
  53.  
  54. const int N = 100005, R = 1 << 20, ABC = 26, logn = 20;
  55. const int BUBEN = 1001;
  56.  
  57. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  58.  
  59. vector<vector<int>> up(N, vector<int>(logn));
  60. vector<vector<int>> mn(N, vector<int>(logn, INF));
  61. vector<int> d(N);
  62.  
  63. int minn(int a, int b) {
  64. if (d[a] < d[b])
  65. swap(a, b);
  66. int ans = INF;
  67. for (int i = logn - 1; i >= 0; i--) {
  68. int pa = up[a][i];
  69. if (d[pa] > d[b]) {
  70. ans = min(ans, mn[a][i]);
  71. a = pa;
  72. }
  73. }
  74. if (d[a] > d[b]) {
  75. ans = min(ans, mn[a][0]);
  76. a = up[a][0];
  77. }
  78.  
  79. if (a == b)
  80. return ans;
  81. for (int i = logn - 1; i >= 0; i--) {
  82. int pa = up[a][i], pb = up[b][i];
  83. if (pa != pb) {
  84. ans = min(ans, min(mn[a][i], mn[b][i]));
  85. a = pa;
  86. b = pb;
  87. }
  88. }
  89. return min(ans, min(mn[a][0], mn[b][0]));
  90. }
  91.  
  92. void dfs(vector<vector<int>>& gr, vector<int>& cost, int v, int pr) {
  93. d[v] = d[pr] + 1;
  94. up[v][0] = pr;
  95. mn[v][0] = cost[v];
  96. for (int i = 1; i < logn; i++) {
  97. up[v][i] = up[up[v][i - 1]][i - 1];
  98. mn[v][i] = min(mn[up[v][i - 1]][i - 1], mn[v][i - 1]);
  99. }
  100.  
  101. for (int u : gr[v]) {
  102. if (pr != u)
  103. dfs(gr, cost, u, v);
  104. }
  105. }
  106.  
  107. signed main() {
  108. ios_base::sync_with_stdio(0);
  109. cin.tie(0);
  110. cout.tie(0);
  111. srand(time(0));
  112. cout.precision(17);
  113.  
  114. int n;
  115. cin >> n;
  116.  
  117. vector<vector<int>> gr(n + 1);
  118. vector<int> cost(n + 1);
  119. for (int i = 2; i <= n; i++) {
  120. int a, b;
  121. cin >> a >> b;
  122. gr[a].pb(i);
  123. cost[i] = b;
  124. }
  125.  
  126. dfs(gr, cost, 1, 1);
  127.  
  128. int q;
  129. cin >> q;
  130.  
  131. while (q--) {
  132. int a, b;
  133. cin >> a >> b;
  134.  
  135. cout << minn(a, b) << endl;
  136. }
  137. return 0;
  138. }
  139.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement