Timus 2109

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int ras = 200010, n, l, timer, q;

vector <int> tin, tout, h, aga, tree;
vector <vector <int>> grafs, up;


void dfs(int v, int p = 1, int hh = 0) {
    tin[v] = ++timer;
    h[v] = hh;
    up[v][0] = p;
    for (int i = 1; i <= l; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }

    for (int i = 0; i < grafs[v].size(); i++) {
        int to = grafs[v][i];
        if (to != p) {
            dfs(to, v, hh + 1);
        }
    }

    tout[v] = ++timer;
}

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

int lca(int a, int b) {
    if (upper(a, b))  return a;
    if (upper(b, a))  return b;
    for (int i = l; i >= 0; i--)
        if (!upper(up[a][i], b))
            a = up[a][i];
    return up[a][0];
}

void build(int pos, int beg, int end) {
    if (beg == end) {
        tree[pos] = aga[beg];
    }
    else {
        int prom = (beg + end) / 2;
        build(2 * pos, beg, prom);
        build(2 * pos + 1, prom + 1, end);
        if (h[tree[2 * pos]] < h[tree[2 * pos + 1]]) {
            tree[pos] = tree[2 * pos];
        }
        else {
            tree[pos] = tree[2 * pos + 1];
        }
    }
}

int minim(int pos, int beg, int end, int l, int r) {
    if (l > r) {
        return 0;
    }
    if (beg == l && end == r) {
        return tree[pos];
    }

    int prom = (beg + end) / 2;
    int k1 = minim(2 * pos, beg, prom, l, min(r, prom));
    int k2 = minim(2 * pos + 1, prom + 1, end, max(prom + 1, l), r);
    if (h[k1] < h[k2]) {
        return k1;
    }
    else {
        return k2;
    }
}


int main()
{
    iostream::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;

    grafs.resize(n + 1); tin.resize(n + 1); tout.resize(n + 1); up.resize(n + 1); h.resize(n + 1); aga.resize(n + 1), tree.resize(2000000);

    for (int i = 0; i < (n - 1); i++) {
        int fr, to;

        cin >> fr >> to;

        grafs[fr].push_back(to);
        grafs[to].push_back(fr);
    }

    l = 0;
    int y = n;
    while (y > 0) {
        l++;
        y /= 2;
    }

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

    dfs(1, 1, 0);
    cin >> q;
    h[0] = n + 1;
    for (int i = 1; i < n; i++) {
        aga[i] = lca(i, i + 1);
    }
    if (n > 1) {
        build(1, 1, n - 1);
    }

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