LCA (Binary Lifting)

#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define F first
#define S second

using namespace std;
typedef long long ll;
typedef long double ld;
const double pi = acos(-1.0);
const double eps = 1e-9;
ll dx[4] = {0, 1, 0, -1};
ll dy[4] = {1, 0, -1, 0};

const ll INF = 1e7;
const int MX = 2e5 + 9;
const int MN = 20;

vector <int> adj[MX];
int in[MX], out[MX], t = 0, l;
int up[MX][MN];

void DFS (int v, int p) {
    in[v] = ++t;
    up[v][0] = p;
    for (int i = 1; i <= l; i++)
        up[v][i] = up[up[v][i - 1]][i - 1];
    for (auto u: adj[v]) {
        if (u == p) continue;
        DFS (u, v);
    }
    out[v] = ++t;
}

bool chk (int u, int v) {
    return (in[u] <= in[v]) && (out[u] >= out[v]);
}

int lca (int u, int v) {
    if (chk(u, v)) return u;
    if (chk(v, u)) return v;
    for (int i = l; i >= 0; i--)
        if (!chk(up[u][i], v))
            u = up[u][i];
    return up[u][0];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    l = log2(n);
    DFS (1, 1);
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;
    }
    return 0;
}