Submission #230649

---

Source Code Expand

#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define P pair<int, int>
const int MAX_V = 100010;
const int MAX_LOG_V = 17;

vector<int> G[MAX_V];
int root = 0;

int parent[MAX_LOG_V][MAX_V];
int 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 dist[MAX_V];

void make_dist(int n, int now, int d){
  dist[now] = d;
  REP(i, G[now].size()){
    int next = G[now][i];
    if(dist[next] != -1) continue;
    make_dist(n, next, d + 1);
  }
}

int main(){
  memset(dist, -1, sizeof(dist));
  int N; cin >>N;
  REP(i, N - 1){
    int a, b; cin >>a >>b;
    G[a - 1].push_back(b - 1);
    G[b - 1].push_back(a - 1);
  }
  make_dist(N, 0, 0);
  init(N);
  int Q; cin >>Q;
  REP(i, Q){
    int a, b; cin >>a >>b;
    int p = lca(a - 1, b - 1);
    //cout <<a - 1 <<", " <<b - 1 <<", " <<p <<endl;
    cout <<(dist[a - 1] + dist[b - 1] - 2 * dist[p]) + 1 <<endl;
  }
  return 0;
}

Submission Info

Judge Result