LCA

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100000; // максимальное количество вершин
const int MAXK = 20;     // степень двойки, до которой считаем подъем

int n;                   // количество вершин
vector<int> v[MAXN];     // список смежности для каждой вершины
int p[MAXN];             // непосредственный предок (родитель)
int pr[MAXN][MAXK];      // массив переходов по степеням двойки
int t1[MAXN];            // время входа в вершину
int t2[MAXN];            // время выхода из вершины
int ct;                  // текущее время

void dfs(int x, int p) {
    // x - текущая вершина, p - её родитель
    t1[x] = ct++;
    ::p[x] = p;  // сохраняем предка в глобальном массиве

    for (int y : v[x]) {
        if (y == p)
            continue;
        dfs(y, x);
    }

    t2[x] = ct++;
}

// функция считает переходы по степеням двойки
void calcBinary() {
    for (int i = 0; i < n; i++)
        pr[i][0] = p[i];  // подъем на 2^0 - это переход в непосредственного предка

    for (int k = 1; k < MAXK; k++)
        for (int x = 0; x < n; x++) {
            int y = pr[x][k - 1];  // поднялись на 2^(k-1)
            int z = pr[y][k - 1];  // поднялись еще на 2^(k-1)
            pr[x][k] = z;          // сохраняем результат - поднялись в сумме на 2^k
        }
}

// функция проверяет, является ли x предком y (т.е. лежит ли y в поддереве вершины x)
bool checkParent(int x, int y) {
    return t1[x] <= t1[y] && t2[x] >= t2[y];
}

// функция находит наименьшего общего предка
int lca(int x, int y) {
    if (checkParent(x, y))  // если x уже предок y, то ответ x
        return x;

    for (int k = MAXK - 1; k >= 0; k--) {
        int z = pr[x][k];  // поднимаемся от x на 2^k
        if (!checkParent(z, y))
            x = z;  // если мы все еще не стали предком y, то сохраняем этот переход
    }

    return p[x];  // в итоге мы оказались на одну вершину ниже lca,
                  // поэтому возвращаем ее предка
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        // считываем ребра
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(0, 0);     // считаем массивы t1, t2, p
    calcBinary();  // считаем массив pr

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        // отвечаем на запросы - для пары вершин найти общего предка
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
}