Advertisement
ivnikkk

Untitled

Aug 3rd, 2022
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. #define int long long
  6. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  7. const int inf = 1e18;
  8. const int LG = 17;
  9. const int N = 1e5 + 1;
  10. int up[LG][N] = {}, d[N];
  11. int up_min[LG][N];
  12. int t = 0;
  13. vector<vector<pair<int,int>>> gr;
  14. void dfs(int v, int p) {
  15.     for (int l = 1; l < LG; l++) {
  16.         up[l][v] = up[l - 1][up[l - 1][v]];
  17.         up_min[l][v] = min(up_min[l - 1][v], up_min[l - 1][up[l - 1][v]]);
  18.     }
  19.     if (p == -1) {
  20.         d[v] = 0;
  21.         up[0][v] = 0;
  22.         up_min[0][v] = inf;
  23.     }
  24.     else {
  25.         d[v] = d[p] + 1;
  26.     }
  27.     for (auto&& [u, w] : gr[v]) {
  28.         if (u != p) {
  29.             up[0][u] = v;
  30.             up_min[0][u] = w;
  31.             dfs(u, v);
  32.         }
  33.     }
  34. }
  35. int get_mn(int a, int b) {
  36.     int ans = inf;
  37.     if (a == b)return a;
  38.     if (d[b] > d[a])swap(a, b);
  39.     for (int i = LG - 1; i >= 0; i--) {
  40.         if (d[up[i][a]] >= d[b]) {
  41.             ans = min(ans, up_min[i][a]);
  42.             a = up[i][a];
  43.         }
  44.     }
  45.     if (a == b) return ans;
  46.     for (int i = LG - 1; i >= 0; i--) {
  47.         if (up[i][a] != up[i][b]) {
  48.             ans = min(ans, min(up_min[i][a], up_min[i][b]));
  49.             a = up[i][a], b = up[i][b];
  50.         }
  51.     }
  52.     return min(ans, min(up_min[0][b],up_min[0][a]));
  53. }
  54. signed main() {
  55. #ifdef _DEBUG
  56.     freopen("input.txt", "r", stdin);
  57.     freopen("output.txt", "w", stdout);
  58. #endif
  59.     ios_base::sync_with_stdio(false);
  60.     cin.tie(nullptr);
  61.     cout.tie(nullptr);
  62.     int n, m; cin >> n;
  63.     gr.resize(n);
  64.     for (int i = 1; i < n; i++) {
  65.         int v, w; cin >> v >> w;
  66.         v--;
  67.         gr[v].push_back({ i,w });
  68.         gr[i].push_back({ v,w });
  69.     }
  70.     for (int i = 0; i < LG; i++) {
  71.         for (int j = 0; j < n; j++) {
  72.             up_min[i][j] = inf;
  73.         }
  74.     }
  75.     dfs(0, -1);
  76.     int q; cin >> q;
  77.     for (int i = 0; i < q; i++) {
  78.         int a, b;
  79.         cin >> a >> b;
  80.         a--, b--;
  81.         cout << get_mn(a, b) << '\n';
  82.     }
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement