Least Common Ancestor (LCA) Example

/*
 * Coded with love :3
 */
#include <bits/stdc++.h>

typedef long long int ll;
typedef unsigned long long int ull;

#define pb push_back
#define fr first
#define sc second
#define th third
#define all(a) a.begin(), a.end()
#define newline cout << "\n";
#define scan(a) for(int i=0; i < (int)(sizeof(a) / sizeof(a[0])) ; i++) cin >> a[i];
#define print(a) for(int i=0; i < (int)(sizeof(a) / sizeof(a[0])) ; i++) cout << a[i] << " ";
#define tie() ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;

const int N   = 1000*100*2+1000;
const int INF = 1000*1000*1000+1000;
const int mod = 1000*1000*1000+7;

using namespace std;

int logN = 1;
vector < vector <int> > g, up;
vector <int> tin, tout;

int t = 1;

void dfs(int v, int p) {
    tin[v] = t++;
    up[v][0] = p;

    for(int i=1; i <= logN; i++)
        up[v][i] = up[ up[v][i-1] ][i-1];

    for(auto to : g[v]) {
        if(to != p)
            dfs(to, v);
    }

    tout[v] = t++;
}

bool parent(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
    if(parent(a, b)) return a;
    if(parent(b, a)) return b;

    for(int i=logN; i >= 0; i--) {
        if(!parent(up[a][i], b))
            a = up[a][i];
    }

    return up[a][0];
}

int main() {
    tie();

    // Vertexes, edges
    int n, m;
    cin >> n >> m;

    tin.assign(n, 0);
    tout.assign(n, 0);
    up.resize(n);
    g.resize(n);

    for(int i=0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].pb(b);
    }

    while((1<<logN) <= n)
        { logN++; }

    for(int i=0; i < n; i++)
        { up[i].resize(logN + 1); }

    dfs(0, 0);

    int q;
    cin >> q;

    for(int i=0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        cout << lca(a, b)+1 << "\n";
    }

    return 0;
}