binarylifting2.cpp

#include <bits/stdc  .h>
using namespace std ;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;

#define ll long long
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define For(i,a,b) for (ll i = a ; i < b ; i  )
#define Forr(i,a,b) for (ll i = a ; i >= b; i--)
#define F first
#define S second
#define vl vector<ll>
#define pb push_back
#define pll pair<ll,ll>
#define mp make_pair
#define endl '\n'

// template <class T, class cmp = less<T>> using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;

ll modulo = (ll)1e9   7;

ll fpow(ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b&1) ans = (ans*a)%modulo;
		a = (a*a)%modulo;
		b = b>>1; 
	}
	return ans;
}

const ll N = 2e5   10;
const ll K = 19;
ll parent[N][K];
ll depth[N]; 
vl G[N];
ll tin[N];
ll tout[N];
ll t;
 
void init()
{
	For(i,0,N)
	{
		For(j,0,K)
		{
			parent[i][j] = 0;
		}
		depth[i] = 0;
		G[i].clear();
	}
	t = 0;
}
 
void dfs(ll u, ll par)
{	
	parent[u][0] = par;
	depth[u] = depth[par]   1;		
	tin[u] =   t;
	For(i,1,K)
	{ 
		parent[u][i] = parent[parent[u][i-1]][i-1];
	}
 	For(i,0,(ll)G[u].size())
 	{
 		ll k = G[u][i];
 		if (k == par)
 		{
 			continue;
 		}
 		dfs(k,u);
 	}
 	tout[u] =   t;
}

bool isAncestor(ll u, ll v)
{
	return (tin[u] <= tin[v] and tout[v] <= tout[u]);
}

ll lca(ll u, ll v)
{
	if(isAncestor(u,v))
	{
    	return u;
	}
  	if(isAncestor(v,u))
  	{
    	return v;
  	}
	ll x = u;
	Forr(i,K-1,0)
	{
		if(isAncestor(parent[x][i],v))
		{
			continue;
		}
		x = parent[x][i];
	}
  	return parent[x][0];
}

void addEdge(ll u, ll v)
{
	G[u].pb(v);
	G[v].pb(u);
}

void solve () 
{
	init();

	ll n, q;
	cin >> n >> q;

	For(i,0,n-1)
	{
		ll u; cin >> u;
		ll v; cin >> v;
		addEdge(v,u);
	}

	dfs(1,0);

	For(i,0,q)
	{
		ll u, v;
		cin >> u >> v;
		cout << lca(u,v) << endl;
	}
}


signed main () 
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin) ;
    	freopen("output.txt","w",stdout) ;
	#endif

    	fast_io();
	int t = 1 ;
	// cin >> t ;
	while (t--) solve() ;  

	return 0 ;
}