Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
1 result

URI1135.cpp

Blame
  • URI1135.cpp 1.80 KiB
    #include <bits/stdc++.h>
    
    #define MAX 101010
    #define MOD 1000000007
    #define inf 0x3f3f3f3f
    #define MAXLOG 20
    
    #define fi first
    #define se second
    #define sz size()
    #define pb push_back
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<ll,ll> ii;
    
    vector<ii> graph[MAX];
    
    ll h[MAX];
    ll par[MAX][MAXLOG], cost[MAX][MAXLOG];
    
    void dfs(int v, int p = -1, ll c = 0) {
      par[v][0] = p;
      cost[v][0] = c;
    
      if (p + 1)
        h[v] = h[p] + 1;
    
      for (int i = 1; i < MAXLOG; ++i)
        if (par[v][i - 1] + 1) {
          par[v][i] = par[par[v][i - 1]][i - 1];
          cost[v][i] += cost[v][i - 1] + cost[par[v][i - 1]][i - 1];
        }
    
      for (auto u : graph[v]) 
        if (p != u.fi)
          dfs(u.fi, v, u.se);
    }
    
    
    void preprocess(int v) {
      memset(par, -1, sizeof par);
      memset(cost, 0, sizeof cost);
      dfs(v);
    }
    
    
    ll query(int p, int q) {
      ll ans = 0;
    
      if (h[p] < h[q])
        swap(p, q);
    
      for (int i = MAXLOG - 1; i >= 0; --i)
        if (par[p][i] + 1 && h[par[p][i]] >= h[q]) {
          ans += cost[p][i];
          p = par[p][i];
        }
    
      if (p == q)
        return ans;
    
      for (int i = MAXLOG - 1; i >= 0; --i)
        if (par[p][i] + 1 && par[p][i] != par[q][i]) {
          ans += cost[p][i] + cost[q][i];
          p = par[p][i];
          q = par[q][i];
        }
    
      if (p == q) return ans;
      else return ans + cost[p][0] + cost[q][0];
    }
    
    int main() {
      ll li;
      int ai, n;
      int q, s, t;
    
      while (scanf("%d", &n) && n) {
        for (int i = 0; i < n + 1; ++i)
          graph[i].clear();
    
        for (int i = 1; i <= n - 1; ++i) {
          scanf("%d %lld", &ai, &li);
          graph[ai].pb(ii(i, li)); 
        }
    
        preprocess(0);
    
        scanf("%d", &q);
        for (int i = 0; i < q; ++i) {
          scanf("%d %d", &s, &t);
          if (i) printf(" ");
          printf("%lld", query(s, t));
        }
        printf("\n");
      }
    
      return 0;
    }