Algo Project 1

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

const int N = 1e5 + 5e1;
const int OO = INT_MAX;
int Tree[N][2] ,Par[N];
vector< int > Dist;
int n ,Q;

vector< int > GetLcaPath(int u ,int v){
    vector< int > PathV;
    vector< int > PathU;

        while( u != v ){
                if( Dist[u] < Dist[v] ){
                        PathV.push_back(v);
                        v = Par[v];
                } else if( Dist[u] > Dist[v] ){
                        PathU.push_back(u);
                        u = Par[u];
                } else {
                        PathV.push_back(v);
                        PathU.push_back(u);
                        u = Par[u];
                        v = Par[v];
                }
        } PathV.push_back( v );

        for(int i = PathU.size() - 1 ; i >= 0 ; i --) PathV.push_back( PathU[i] );
    return PathV;
}

void BFS() {
        Dist.assign(n + 1 ,OO);
        queue< int > Q;
        Dist[1] = 0;
        Q.push(1);

        while( !Q.empty() ) {
                int front = Q.front(); Q.pop();

                for(int i=0 ; i < 2 ; i++){
                        if( Tree[front][i] != -1 && Dist[Tree[front][i]] == OO ){
                                Dist[ Tree[front][i] ] = Dist[front] + 1;
                                Q.push( Tree[front][i] );
                        }
                }
        }
}

void Solve(){
        int u ,v ,Ans;
        scanf("%d%d" ,&u ,&v);

        vector< int > Path = GetLcaPath(u ,v);
        Ans = Path[ (int)Path.size() / 2 ];
        printf("%d\n" ,Ans);
}

int main() {
        scanf("%d" ,&n);
        for(int i=1 ; i <= n ; i++) {
                int L ,R; scanf("%d%d" ,&L ,&R);
                Tree[i][0] = L;
                Tree[i][1] = R;
                Par[L] = Par[R] = i;
        }

        BFS();

        scanf("%d" ,&Q);
        while( Q-- ) Solve();
    return 0;
}