Submission #1367868

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define MAX_V 100001
 
int dep[MAX_V], par[MAX_V][19];
vector<int> G[MAX_V];
void dfs(int v,int u,int d){
  dep[v]=d;
  for(int i=0; i<G[v].size(); i++){
    int w=G[v][i];if(w==u) continue;
    par[w][0]=v;dfs(w,v,d+1);
  }
}
int lcp(int a,int b){
  if(dep[a]<dep[b]) swap(a,b);
  for(int i=0; i<19; i++){
    if(((dep[a]-dep[b])&(1<<i))) a=par[a][i];
  }
  if(a==b) return a;
  for(int i=18;i>=0;i--){
    if(par[a][i]!=par[b][i]) a=par[a][i],b=par[b][i];
  }
  return par[a][0];
}
void lca() {
  memset(par,0,sizeof(par));
  dfs(0,-1,0);
  for(int i=0; i<18; i++) for(int j=0; j<MAX_V; j++) par[j][i+1]=par[par[j][i]][i];
}
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);
  }
  lca();
  int m;
  cin >> m;
  for(int i=0; i<m; i++) {
    int x,y;
    cin >> x >> y;
    x--;y--;
    cout << dep[x]+dep[y]-2*dep[lcp(x,y)]+1 << endl;
  }
  return 0;
}

Submission Info

Judge Result