UVa12238

UVa12238
クエリー(A, B)が与えられたとき、答えは
ルートからのAまで距離 + ルートからBまでの距離 - ルートからAとBの最近共通祖先までの距離 * 2
参考URL

// UVa 12238
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long int lli;

const int NODE = 100000 + 1;
//const int DEPTH = (int)(log((double)NODE) / log(2.0) + 1.0);
const int DEPTH = 18;

// T: dp table
// P: parent,first ancestor
// L: level, depth
int T[NODE][DEPTH], P[NODE], L[NODE];

int addLevel(int node)
{
  if (L[node] != -1) return L[node];
  else return L[node] = addLevel(P[node]) + 1;
}

// ! keep P[root] = root
void LCA(const int &node)
{  
  const int root = 0;
  fill(L, L + node, -1);
  L[root] = 0;
  for (int i = 0; i < node; ++i) {
    L[i] = addLevel(i);
  }

  fill(&T[0][0], &T[NODE - 1][DEPTH], -1);
  for (int i = 0; i < node; ++i) {
    T[i][0] = P[i];    
  }
  for(int j = 1; (1 << j) < node; ++j){
    for (int i = 0; i < node; ++i) {
      if (T[i][j - 1] != -1) {
        T[i][j] = T[T[i][j - 1]][j - 1];
      }
    }
  }
  
  return ; 
}

int query(const int &node,  int a, int b)
{
  if (L[a] < L[b]) swap(a, b);

  int lg = 1;
  while ((1 << lg) <= L[a]) ++lg;
  --lg;

  for (int i = lg; 0 <= i; --i) { 
    if (L[a] - (1 << i) >= L[b]) {
      a = T[a][i];
    }
  }

  if (a == b) return a;
  for (int i = lg; 0 <= i; --i) {
    if (T[a][i] != -1 && T[a][i] != T[b][i]) {
      a = T[a][i];
      b = T[b][i];
    }
  }
  
  return P[a];
}

void rec(int node, lli cost[], vector< pair<int, lli> > e[], lli sum) 
{
  cost[node] = sum;
  for (int i = 0; i < e[node].size(); ++i) {    
    rec(e[node][i].first, cost, e, sum + e[node][i].second);
  }
  return ;
}

int main(void)
{
  int node;
  while (scanf("%d", &node) && node) {

    vector< pair<int, lli> > e[node];
    for (int i = 1; i < node; ++i) {
      lli cost;
      scanf("%d%lld", P + i, &cost);
      e[P[i]].push_back(make_pair(i, cost));
    }
   
    static lli cost[NODE];
    fill(cost, cost + node, 0LL);
    rec(0, cost, e, 0);

    const int root = 0;
    P[root] = root;
    LCA(node);

    int q, a, b;
    scanf("%d", &q);
    while (q--) {
      scanf("%d%d", &a, &b);
      int lca = query(node, a, b);
      printf("%lld", cost[a] + cost[b] - cost[lca] * 2LL);
      if (q) printf(" ");
    }
    puts("");
  }  
  return 0;
}