Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <cmath>
- struct Edge;
- namespace {
- using Num = int64_t;
- using NumsVec = std::vector<Num>;
- using VecNumsVec = std::vector<NumsVec>;
- using NumsPair = std::pair<Num, Num>;
- using NumsPairVec = std::vector<NumsPair>;
- using BoolVec = std::vector<bool>;
- using EdgeVec = std::vector<Edge>;
- using VecEdgeVec = std::vector<EdgeVec>;
- }
- const Num INF = Num(1e15);
- std::istream& operator>>(std::istream& input, NumsPairVec& vec) {
- for (auto& elem : vec) {
- std::cin >> elem.first >> elem.second;
- --elem.first;
- }
- return input;
- }
- struct Tree {
- Tree(NumsPairVec& parents) : log(std::log2(size) + 5), size(parents.size() + 1), p(size, 0), dist(size, 0), tin(size, 0), tout(size, 0),
- d(size, 0), children(size), dp(size, NumsVec(log + 1, 0)), dp_dist(size, NumsVec(log + 1, 0)) {
- for (size_t v = 1; v < size; ++v) {
- p[v] = parents[v - 1].first;
- dist[v] = parents[v - 1].second;
- if (p[v] != -1) {
- children[p[v]].push_back(v);
- } else {
- root = v;
- }
- }
- p[root] = 0;
- PreCount(root);
- };
- void PreCount(int64_t v) {
- tin[v] = time++;
- euler.push_back(v);
- if (p[v] != v) d[v] = d[p[v]] + 1;
- dp[v][0] = p[v];
- dp_dist[v][0] = dist[v];
- for (size_t i = 1; i < log; ++i) {
- dp[v][i] = dp[dp[v][i - 1]][i - 1];
- dp_dist[v][i] = dp_dist[v][i - 1] + dp_dist[dp[v][i - 1]][i - 1];
- }
- for (auto u : children[v]) {
- PreCount(u);
- }
- euler.push_back(v);
- tout[v] = time++;
- }
- bool IsAncestor(int64_t p, int64_t v) {
- return tin[p] <= tin[v] && tout[v] <= tout[p];
- }
- int64_t LCA(int64_t u, int64_t v) {
- if (d[u] < d[v]) std::swap(u, v);
- if (IsAncestor(v, u)) return v;
- for (int64_t i = log - 1; i >= 0; --i) {
- if (!IsAncestor(dp[u][i], v)) u = dp[u][i];
- }
- return p[u];
- }
- int64_t MinEdge(int64_t par, int64_t v) {
- int64_t ans = 0;
- for (int64_t i = log - 1; i >= 0; --i) {
- if (d[par] <= d[dp[v][i]]) {
- ans += dp_dist[v][i];
- v = dp[v][i];
- }
- }
- return ans;
- }
- int64_t FindMinEdge(int64_t u, int64_t v) {
- int64_t lca = LCA(u, v);
- return MinEdge(lca, u) + MinEdge(lca, v);
- }
- size_t size = 0;
- int64_t log = 0;
- size_t root = 0;
- size_t time = 0;
- VecNumsVec children;
- VecNumsVec dp;
- VecNumsVec dp_dist;
- NumsVec dist;
- NumsVec p;
- NumsVec tin;
- NumsVec tout;
- NumsVec euler;
- NumsVec d;
- };
- int main() {
- size_t n, q;
- std::cin >> n;
- NumsPairVec parents(n - 1);
- std::cin >> parents;
- Tree tree(parents);
- std::cin >> q;
- while (q--) {
- int64_t u, v;
- std::cin >> u >> v;
- std::cout << tree.FindMinEdge(u - 1, v - 1) << std::endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement