Algo pro log n

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

typedef pair<int,int> ii;
const int N = 1e5 + 5e1;
#define rg (p << 1) | 1
#define lf (p << 1)
#define OO INT_MAX
#define S second
#define F first

int Tree[N][2] ,idx[N];
int n ,Q;

int DfsSpTree[N * 2][2]; /// DFS Spanning Tree
int DfsSize = 1;    /// DFS Spanning Tree Size

class SegTree {
    private:
            vector< ii > Seg;

            ii Compain(ii a ,ii b) {
                    return (a.S < b.S) ? a : b;
            }

            void Build(int p ,int L ,int R){
                    if( L == R ) {
                            Seg[p] = ii( DfsSpTree[L][0] ,DfsSpTree[L][1] );
                            return;
                    }

                    int Mid = (L + R) >> 1;
                    Build(lf ,L ,Mid);
                    Build(rg ,Mid + 1 ,R);
                    Seg[p] = Compain(Seg[lf] ,Seg[rg]);
            }

            ii QRY(int i ,int j ,int p ,int L ,int R){
                    if( i >  R || L >  j ) return ii(OO ,OO);
                    if( i <= L && R <= j ) return Seg[p];

                    int Mid = (L + R) >> 1;
                    ii LF  = QRY(i ,j ,lf ,L ,Mid);
                    ii RG  = QRY(i ,j ,rg ,Mid + 1 ,R);
                    return Compain(LF ,RG);
            }

    public:
            void Build() {
                    Build(1 ,1 ,DfsSize - 1);
            }
            void ReSize(int n) {
                    Seg.assign(n * 4 ,ii(0,OO));
            }
            ii QRY(int L ,int R) {
                    return QRY(L ,R ,1 ,1 ,DfsSize - 1);
            }
} ST ;

void Dfs_Pre_Order(int u = 1 ,int Depth = 1) {
        DfsSpTree[ DfsSize ][0] = u;
        DfsSpTree[ DfsSize ][1] = Depth;

        if(idx[u] == -1) idx[u] = DfsSize;
        DfsSize ++;

        for(int j = 0 ; j < 2 ; j++){
                int v = Tree[u][j];
                if( v != -1 ){
                        Dfs_Pre_Order(v ,Depth + 1);
                        DfsSpTree[ DfsSize ][0] = u;
                        DfsSpTree[ DfsSize ][1] = Depth;
                        DfsSize++;
                }
        }
}

/// ------------------------------------------------------------------ ///

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

        int L = idx[u] ,R = idx[v];
        if( L > R )swap(L ,R);
        ii Ans = ST.QRY(L ,R);

        printf("%d\n" ,Ans.F);
}

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;
        }

        memset(idx ,-1 ,sizeof idx);
        Dfs_Pre_Order();

        ST.ReSize(DfsSize + 1);
        ST.Build();

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


/// --- \STUFF --- ///
/*
    void PrintDfsSpTree(){
        cout << "DFS ST Size = " << DfsSize << endl;
        for(int i = 1 ; i < DfsSize ; i++)
            cout << DfsSpTree[i][0] << ' '; cout << endl;
        for(int i = 1 ; i < DfsSize ; i++)
            cout << DfsSpTree[i][1] << ' '; cout << endl;
    }

/// --- \TestCases --- ///

INPUT:
6
2 3
4 5
-1 -1
6 -1
-1 -1
-1 -1
2
2 3
6 3

OUTPUT:
1
2
---------------------------------

INPUT:
7
2 3
4 5
-1 6
-1 -1
-1 7
-1 -1
-1 -1
4
5 6
4 3
7 6
6 1

OUTPUT:
1
1 || 2
1 || 2
3
---------------------------------

INPUT:
14
2 3
4 5
6 7
10 -1
-1 -1
8 9
-1 -1
11 12
13 14
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
10
11 7
10 5
8 9
6 1
13 8
13 14
9 7
4 5
10 12
2 8

OUTPUT:


*/