Advertisement
dan_sml

Untitled

Jun 14th, 2022
760
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5. #include <cmath>
  6.  
  7. struct Edge;
  8.  
  9. namespace {
  10.     using Num = int64_t;
  11.     using NumsVec = std::vector<Num>;
  12.     using VecNumsVec = std::vector<NumsVec>;
  13.     using NumsPair = std::pair<Num, Num>;
  14.     using NumsPairVec = std::vector<NumsPair>;
  15.     using BoolVec = std::vector<bool>;
  16.     using EdgeVec = std::vector<Edge>;
  17.     using VecEdgeVec = std::vector<EdgeVec>;
  18. }
  19.  
  20. const Num INF = Num(1e15);
  21.  
  22. std::istream& operator>>(std::istream& input, NumsPairVec& vec) {
  23.     for (auto& elem : vec) {
  24.         std::cin >> elem.first >> elem.second;
  25.         --elem.first;
  26.     }
  27.     return input;
  28. }
  29.  
  30. struct Tree {
  31.     Tree(NumsPairVec& parents) : log(std::log2(size) + 5), size(parents.size() + 1), p(size, 0), dist(size, 0), tin(size, 0), tout(size, 0),
  32.     d(size, 0), children(size), dp(size, NumsVec(log + 1, 0)), dp_dist(size, NumsVec(log + 1, 0)) {
  33.         for (size_t v = 1; v < size; ++v) {
  34.             p[v] = parents[v - 1].first;
  35.             dist[v] = parents[v - 1].second;
  36.             if (p[v] != -1) {
  37.                 children[p[v]].push_back(v);
  38.             } else {
  39.                 root = v;
  40.             }
  41.         }
  42.         p[root] = 0;
  43.         PreCount(root);
  44.     };
  45.  
  46.     void PreCount(int64_t v) {
  47.         tin[v] = time++;
  48.         euler.push_back(v);
  49.         if (p[v] != v) d[v] = d[p[v]] + 1;
  50.         dp[v][0] = p[v];
  51.         dp_dist[v][0] = dist[v];
  52.         for (size_t i = 1; i < log; ++i) {
  53.             dp[v][i] = dp[dp[v][i - 1]][i - 1];
  54.             dp_dist[v][i] = dp_dist[v][i - 1] + dp_dist[dp[v][i - 1]][i - 1];
  55.         }
  56.         for (auto u : children[v]) {
  57.             PreCount(u);
  58.         }
  59.         euler.push_back(v);
  60.         tout[v] = time++;
  61.     }
  62.  
  63.     bool IsAncestor(int64_t p, int64_t v) {
  64.         return tin[p] <= tin[v] && tout[v] <= tout[p];
  65.     }
  66.  
  67.     int64_t LCA(int64_t u, int64_t v) {
  68.         if (d[u] < d[v]) std::swap(u, v);
  69.         if (IsAncestor(v, u)) return v;
  70.         for (int64_t i = log - 1; i >= 0; --i) {
  71.             if (!IsAncestor(dp[u][i], v)) u = dp[u][i];
  72.         }
  73.         return p[u];
  74.     }
  75.  
  76.     int64_t MinEdge(int64_t par, int64_t v) {
  77.         int64_t ans = 0;
  78.         for (int64_t i = log - 1; i >= 0; --i) {
  79.             if (d[par] <= d[dp[v][i]]) {
  80.                 ans += dp_dist[v][i];
  81.                 v = dp[v][i];
  82.             }
  83.         }
  84.         return ans;
  85.     }
  86.  
  87.     int64_t FindMinEdge(int64_t u, int64_t v) {
  88.         int64_t lca = LCA(u, v);
  89.         return MinEdge(lca, u) + MinEdge(lca, v);
  90.     }
  91.  
  92.     size_t size = 0;
  93.     int64_t log = 0;
  94.     size_t root = 0;
  95.     size_t time = 0;
  96.  
  97.     VecNumsVec children;
  98.     VecNumsVec dp;
  99.     VecNumsVec dp_dist;
  100.     NumsVec dist;
  101.     NumsVec p;
  102.     NumsVec tin;
  103.     NumsVec tout;
  104.     NumsVec euler;
  105.     NumsVec d;
  106. };
  107.  
  108. int main() {
  109.     size_t n, q;
  110.     std::cin >> n;
  111.     NumsPairVec parents(n - 1);
  112.     std::cin >> parents;
  113.     Tree tree(parents);
  114.     std::cin >> q;
  115.     while (q--) {
  116.         int64_t u, v;
  117.         std::cin >> u >> v;
  118.         std::cout << tree.FindMinEdge(u - 1, v - 1) << std::endl;
  119.     }
  120. }
  121.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement