Day1 - LCA+segTree.cpp

#include <bits/stdc++.h>
using namespace std;


const int MAXN = 1e5 + 1;
const int INF = 1e9;

pair <int, int> st[8 * MAXN];
int h[MAXN], pos[MAXN];
vector <int> dfsorder;

void build (int id, int l, int r) {
    if (l == r) {
        st[id] = make_pair (h[dfsorder[l]], dfsorder[l]);
        return;
    }

    int mid = (l + r) / 2;
    build (id * 2, l, mid);
    build (id * 2 + 1, mid + 1, r);

    st[id] = min (st[id * 2], st[id * 2 + 1]);

    return;
}

pair <int, int> query (int id, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) return st[id];
    if (r < ll || rr < l) {
        return make_pair (INF, -1);
    }

    int mid = (l + r) / 2;
    return min (query (id * 2, l, mid, ll, rr),
                query (id * 2 + 1, mid + 1, r, ll, rr));
}

vector <int> g[MAXN];

void dfs (int x, int pai) {
    pos[x] = dfsorder.size();
    dfsorder.push_back (x);

    for (int i = 0; i < g[x].size(); ++i) {
        int y = g[x][i];
        if (y == pai) continue;

        h[y] = h[x] + 1;
        dfs (y, x);

        dfsorder.push_back (x);
    }
}

int main () {

    int n;
    cin >> n;

    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back (b);
        g[b].push_back (a);
    }

    h[0] = 0;
    dfs (0, -1);

    build (1, 0, dfsorder.size() - 1);

    int q;
    cin >> q;

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;

        cout << "LCA de " << a << " e " << b << " = ";

        a--; b--;

        if (pos[a] < pos[b])
            cout << query (1, 0, dfsorder.size() - 1, pos[a],
            pos[b]).second << endl;
        else
            cout << query (1, 0, dfsorder.size() - 1, pos[b],
            pos[a]).second << endl;

    }



    return 0;
}