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; }