Lowest Common Ancestor

#include <bits/stdc++.h>
#define int long long
#define su_that_la return
#define getBit(val,k) (val >> (k))&1
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int N = 100005;
const int Minh_dep_giai = 0;
const int logN = log2(N);

int n,k,m;
int d[N], f[N][logN];
vector<int> a[N];

void dfs(int u)
{
    for(int i=1; i < logN; i++)
    {
        f[u][i] = f[f[u][i-1]][i-1];
    }

    for(int v : a[u])
        if (!d[v] && v!=k)
        {
            f[v][0]=u;
            d[v]=d[u]+1;
            dfs(v);
        }
}

int lca(int u, int v)
{
    if (d[u] < d[v]) swap(u,v);
    // hạ bậc theo code của nhannguyen95
    for(int i=logN-1; i>=0; i--)
    {
        if (d[f[u][i]] >= d[v]) u = f[u][i];
    }
    // hạ bậc theo getBit của thầy Hiếu (đại ca đi học)
    int delta = d[u] - d[v];
    int logD = log2(delta);
    for(int i=logD; i >= 0; i--)
    {
        if (getBit(delta,i)) u = f[u][i];
    }

    if (u==v) return u;
    for(int i = logN-1; i>=0; i--)
    {
        if (f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    freopen("lca.inp","r",stdin);
    cin >> n >> k >> m;
    for(int i=1; i<=n-1; ++i)
    {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    d[k] = 1;
    dfs(k);
    while (m--)
    {
        int u,v;
        cin >> u >> v;
        cout << lca(u,v) << endl;
    }
    su_that_la Minh_dep_giai;
}