LCA

for distance or ancestor

#include <bits/stdc++.h>
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define PER(I, A, B) for (int I = (A); I >= (B); --I)
#define DB(A) cout<<(A)<<endl;
#define PB push_back
#define Pair pair<int,int>
#define LL long long
using namespace std;
const int maxn=1e6+10;
const int MAX=30+10;
const int inf=0x3f3f3f3f;	
//head 
vector<int >a[maxn];
int fa[maxn][MAX];
int dep[maxn];
int lg[maxn];
void dfs(int now,int fat)
{
	fa[now][0]=fat;
	dep[now]=dep[fat]+1;
	FOR(i,1,lg[dep[now]])
	{
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for (auto to:a[now]) if (to!=fat)
	{
		dfs(to,now);
	}
}
int lca(int x,int y)
{
	int dis=0;
	if (dep[y]>dep[x]) swap(x,y);
	while (dep[x]>dep[y])
	{
		dis+=1<<lg[dep[x]-dep[y]];
		x=fa[x][lg[dep[x]-dep[y]]];
		
	}
	if (x==y) return dis;
	PER(i,lg[dep[x]],0) if (fa[x][i]!=fa[y][i])
	{
		dis+=2*(1<<i);
		x=fa[x][i];
		y=fa[y][i];
	}
	return dis+2;	
}
signed main()
{
	int n;
	scanf("%d",&n);
	FOR(i,1,n-1)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].PB(y);
		a[y].PB(x);
	}
	FOR(i,1,n)
	{
		lg[i]=(int)log2(i);
	}
	dfs(1,0);

#include <bits/stdc++.h>
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define PER(I, A, B) for (int I = (A); I >= (B); --I)
#define lson k*2
#define rson k*2+1
#define fi first
#define se second
#define DB(A) cout<<(A)<<"!"<<endl
#define DB1(A,B,C) cout<<(A)<<" "<<(B)<<" "<<(C)<<endl
#define PB push_back
#define Pair pair<int,int>
#define MP make_pair
#define LL long long
using namespace std;
const int maxn=1e6+10;
const int MAX=30;
const int inf=0x3f3f3f3f;	
//head
vector<int>a[maxn];
int n,m;	

namespace LCA
{
	int fa[maxn][MAX+10];
	int dep[maxn];
	int lg[maxn];
	
	void dfs(int now,int fat)
	{
	    fa[now][0]=fat;
	    dep[now]=dep[fat]+1;
	    for (auto to:a[now]) if (to!=fat)
	    {
	        dfs(to,now);
	    }
	}		
	void init()
	{	    
		FOR(i,1,n)
	    {
	        lg[i]=(int)log2(i);
	    }
	    FOR(i,1,MAX)
	    {
	    	FOR(j,1,n)
	    	{
	    		fa[j][i]=fa[fa[j][i-1]][i-1];
			}
		}
//		FOR(i,1,n) DB(fa[i][0]);
	}
	
	
	int lca(int x,int y)
	{
	    if (dep[y]>dep[x]) swap(x,y);
	    while (dep[x]>dep[y])
	    {
	        x=fa[x][lg[dep[x]-dep[y]]];	        
	    }
	    if (x==y) return x;
	    PER(i,lg[dep[x]],0) if (fa[x][i]!=fa[y][i])
	    {
	        x=fa[x][i];
	        y=fa[y][i];
	    }
	    return fa[x][0];   
	}
}
signed main()
{
//	freopen("t.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int root;
	cin>>n>>m>>root; 
	FOR(i,1,n-1)
	{
		int x,y;
		cin>>x>>y;
		a[x].PB(y);
		a[y].PB(x);
	}	
	LCA::dfs(root,0);
	LCA::init();
	FOR(i,1,m)
	{
		int x,y;
		cin>>x>>y;
		printf("%d
",LCA::lca(x,y));
	}
//	fclose(stdin);
}