Distance Queries

1#include <bits/stdc++.h>
2using namespace std;
3#define int long long
4const int MAXN=200005;
5const int LOG=18;
6vector<int> adj[MAXN];
7int pa[MAXN][LOG], dep[MAXN];
8void dfs(int i){
9  for(auto&x:adj[i]){
10    if(x==pa[i][0]) continue;
11    pa[x][0]=i;
12    dep[x]=dep[i]+1;
13    dfs(x);
14  }
15}
16int lca(int a,int b){
17  if(dep[a]<dep[b]) swap(a,b);
18  for(int j=LOG-1;j>=0;--j)
19    if(dep[pa[a][j]]>=dep[b])
20      a=pa[a][j];
21  if(a==b) return a;
22  for(int j=LOG-1;j>=0;--j)
23    if(pa[a][j]!=pa[b][j])
24      a=pa[a][j],b=pa[b][j];
25  return pa[a][0];
26}
27signed main(){
28  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
29  int n,q; cin>>n>>q;
30  for(int i=1;i<n;++i){
31    int u,v; cin>>u>>v;
32    adj[u].emplace_back(v);
33    adj[v].emplace_back(u);
34  }
35  pa[1][0]=1;
36  dfs(1);
37  for(int j=0;j<LOG-1;++j)
38    for(int i=1;i<=n;++i)
39      pa[i][j+1]=pa[pa[i][j]][j];
40  while(q--){
41    int u,v; cin>>u>>v;
42    cout<<dep[u]+dep[v]-2*dep[lca(u,v)]<<'\n';
43  }
44  return 0;
45}