ProgMe

Untitled

Nov 19th, 2023
845
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include <bits/extc++.h>
  2. #define int int64_t
  3.  
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. const int N = 1e5 + 1;
  8. const int L = 17;
  9.  
  10. int n, timer;
  11. array<int, N> tin, tout;
  12. array<array<int, N>, L> up, mn;
  13. array<vector<pair<int, int>>, N> g;
  14.  
  15. void dfs(int v = 0, int p = -1) {
  16.     tin[v] = timer++;
  17.     for (int l = 1; l < L; l++) {
  18.         up[l][v] = up[l - 1][up[l - 1][v]];
  19.         mn[l][v] = min(mn[l - 1][v], mn[l - 1][up[l - 1][v]]);
  20.     }
  21.  
  22.     for (auto [u, w] : g[v]) {
  23.         if (u != p) {
  24.             up[0][u] = v;
  25.             mn[0][u] = w;
  26.             dfs(u, v);
  27.         }
  28.     }
  29.     tout[v] = timer++;
  30. }
  31.  
  32. bool ancestor(int v, int u) {
  33.     return tin[v] <= tin[u] && tout[v] >= tout[u];
  34. }
  35.  
  36. int lca(int v, int u) {
  37.     if (ancestor(v, u)) {
  38.         return v;
  39.     }
  40.     if (ancestor(u, v)) {
  41.         return u;
  42.     }
  43.     for (int l = L - 1; l >= 0; l--) {
  44.         if (!ancestor(up[l][v], u)) {
  45.             v = up[l][v];
  46.         }
  47.     }
  48.     return up[0][v];
  49. }
  50.  
  51. int min_edge(int v, int u) {
  52.     int cur = lca(v, u);
  53.  
  54.     int ans = numeric_limits<int>::max();
  55.     for (int l = L - 1; l >= 0; l--) {
  56.         if (!ancestor(up[l][v], cur)) {
  57.             ans = min(ans, mn[l][v]);
  58.             v = up[l][v];
  59.         }
  60.         if (!ancestor(up[l][u], cur)) {
  61.             ans = min(ans, mn[l][u]);
  62.             u = up[l][u];
  63.         }
  64.     }
  65.  
  66.     if (!ancestor(v, cur)) {
  67.         ans = min(ans, mn[0][v]);
  68.     }
  69.     if (!ancestor(u, cur)) {
  70.         ans = min(ans, mn[0][u]);
  71.     }
  72.     return ans;
  73. }
  74.  
  75. int32_t main() {
  76.     ios::sync_with_stdio(false);
  77.     cin.tie(nullptr);
  78.  
  79.     cin >> n;
  80.  
  81.     for (int v = 1; v < n; v++) {
  82.         int u;
  83.         cin >> u;
  84.         u--;
  85.  
  86.         int w;
  87.         cin >> w;
  88.  
  89.         g[u].emplace_back(v, w);
  90.         g[v].emplace_back(u, w);
  91.     }
  92.  
  93.     dfs();
  94.  
  95.     int q;
  96.     cin >> q;
  97.     while (q--) {
  98.         int v, u;
  99.         cin >> v >> u;
  100.         v--, u--;
  101.  
  102.         cout << min_edge(v, u) << '\n';
  103.     }
  104. }
  105.  
Advertisement
Add Comment
Please, Sign In to add comment