Algo pro log n 2

#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] ,ListNum[N];
vector< vector <int > > TreeList;
vector< int > Tmp;
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;
        Tmp.push_back(u);

        ListNum[u] = (int)TreeList.size();
        idx[u] = DfsSize;
        DfsSize ++;

        bool NodeIsLeaf = true;
        for(int j = 0 ; j < 2 ; j++){
                int v = Tree[u][j];
                if( v != -1 ){
                        NodeIsLeaf = false;
                        Dfs_Pre_Order(v ,Depth + 1);
                        DfsSpTree[ DfsSize ][0] = u;
                        DfsSpTree[ DfsSize ][1] = Depth;
                        DfsSize++;
                }
        }
        if( NodeIsLeaf ) TreeList.push_back( Tmp );
        Tmp.pop_back();
}

void Memset(int n) {
    for(int i = 0 ; i <= n ; i++)
            idx[i] = ListNum[i] = -1;
}
/// ------------------------------------------------------------------ ///

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

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

        int AncHigh = DfsSpTree[ idx[Ancestor.F] ][1] ,
            Uhigh   = DfsSpTree[ idx[u] ][1],
            Vhigh   = DfsSpTree[ idx[v] ][1];

        int Ans = -1;
        if( Uhigh == Vhigh )
                Ans = Ancestor.F;
        else if( Uhigh > Vhigh ) {
                int NumOfList = ListNum[u];
                int Diff = Vhigh - AncHigh;
                int Mid  = (AncHigh + Uhigh - Diff) >> 1;
                Ans = TreeList[ NumOfList ][ Mid - 1 ];
        }
        else if( Uhigh < Vhigh ) {
                int NumOfList = ListNum[v];
                int Diff = Uhigh - AncHigh;
                int Mid = (AncHigh + Vhigh - Diff) >> 1;
                Ans = TreeList[ NumOfList ][ Mid - 1 ];
        }

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

        Memset(n + 1);
        Dfs_Pre_Order();

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

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