AtCoder BeginnerContest 014 D

解答
根付き木において、頂点 a, b 間を辿る最短パスはの最も近い共通祖先の頂点である。よって LCA を用いて、頂点 a までの深さ + 頂点 b までの深さ - 2*共通祖先の頂点 + 1 が答えとなる。
まだ自力でLCAを書くことが出来ないので蟻本そのままのコードを書いた。

参考（本家の解説）
http://www.slideshare.net/chokudai/abc014

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_V (100010)
#define MAX_LOG_V (18)
 
typedef long long ll;
 
vector<ll> G[MAX_V];
int root;
 
ll parent[MAX_LOG_V][MAX_V];
ll depth[MAX_V];
 
void dfs(int v, int p, int d) {
  parent[0][v] = p;
  depth[v] = d;
  for(int i=0; i<G[v].size(); i++) {
    if(G[v][i] != p) dfs(G[v][i], v, d+1);
  }
}
 
void init(int V) {
  dfs(root, -1, 0);
  for(int k=0; k+1<MAX_LOG_V; k++) {
    for(int v=0; v<V; v++) {
      if(parent[k][v] < 0) parent[k+1][v] = -1;
      else parent[k+1][v] = parent[k][parent[k][v]];
    }
  }
}
 
int lca(int u, int v) {
  if(depth[u] > depth[v]) swap(u, v);
  for(int k=0; k<MAX_LOG_V; k++) {
    if((depth[v] - depth[u]) >> k & 1) {
      v = parent[k][v];
    }
  }
  if(u == v) return u;
  for(int k=MAX_LOG_V - 1; k>=0; k--) {
    if(parent[k][u] != parent[k][v]) {
      u = parent[k][u];
      v = parent[k][v];
    }
  }
  return parent[0][u];
}
 
int main() {
  
  int N; cin >> N;
 
  for(int i=0; i<N-1; i++) {
    int x, y; cin >> x >> y; x--, y--;
    G[x].push_back(y);
    G[y].push_back(x);
  } 
  
  root = 0;
  
  init(N);
  
  int Q; cin >> Q;
  for(int i=0; i<Q; i++) {
    int a, b; cin >> a >> b; a--, b--;
    cout << depth[a] + depth[b] - 2*depth[lca(a, b)] + 1 << endl;
  }
  
  return 0;
}