MO's on Tree- So Close Yet So Far(Codechef)

CODECHEF:So Close Yet So Far(MO's on Tree)
///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define piii pair< int ,pair<int,int> >
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
#define UNIK(v) sort(all(v)),v.resize( unique(all(v)) -v.begin() );
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     70005
#define inf    1000000010
#define MD     1000000007LL
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
int n,Nd[MX+2];
int L[MX+2],P[MX+2][22];
int tmm,St[MX+2],Ed[MX+2];

void Dfs(int u,int p,int l) {
    L[ u ]=l;
    St[ u ]=++tmm;
    Nd[ tmm ]=u;
    P[ u ][ 0 ]=p;
    for(int i=0; i< SZ(G[u]) ; i++) {
        int v=G[u][i];
        if( v==p )continue;
        Dfs( v, u,l+1);
    }
    Ed[ u ]=++tmm;
    Nd[ tmm ]=u;
}

void Par_Sparse( ) {
    for(int j=1; (1<<j)<=n; j++) {
        for(int i=1; i<=n; i++) {
            if( P[i][j-1]!=-1 ) {
                P[i][j]=P[ P[i][j-1] ][ j-1 ];
            }
        }
    }
}

int Kth(int x,int k) {
    int j=0;
    while(k) {
        if(k%2==1)x=P[x][j];
        k/=2,j++;
    }
    return x;
}

int Lca(int x,int y) {
    if( L[x]<L[y] ) swap(x,y);
    x=Kth(x, L[x]-L[y] );
    if( x==y ) return x;
    for(int i=16; i>=0; i--) {
        if( P[x][i]!=P[y][i]) {
            x=P[x][i],y=P[y][i];
        }
    }
    return P[x][0];
}

int sq;
struct data {
    int l,r,id,lc;
    data() {};
    data(int a,int b,int c,int d) {
        l=a,r=b,id=c,lc=d;
    }
    bool friend operator <(data A,data B) {
        if( A.l/sq==B.l/sq ) return A.r<B.r;
        else return ((A.l/sq)<(B.l/sq));
    }
}v[MX+2];

inline int min(int a,int b) {
    return ((a<b)?a:b);
}
inline int max(int a,int b) {
    return ((a>b)?a:b);
}

int ar[MX+2],MP[MX+5];
piii nd[(4*MX)+5]; ///Closest dis,min in seg max in seg;
/// No two nodes have the same value printed on them.

inline void Ins(int id,int l,int r,int p,int f) {
    if( l==r ) {
        if( !f )nd[id].X=nd[id].Y.X=inf,nd[id].Y.Y=-inf;
        else nd[id].Y.X=nd[id].Y.Y=MP[ p ];
        return;
    }
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if( p<=md ) Ins(lft,l,md,p,f);
    else Ins(rgt,md+1,r,p,f);
    if( nd[lft].Y.X==inf && nd[lft].Y.Y==-inf )nd[ id ]=nd[ rgt ];
    else if( nd[rgt].Y.X==inf && nd[rgt].Y.Y==-inf )nd[ id ]=nd[ lft ];
    else {
        nd[ id ].Y.X=min(nd[lft].Y.X,nd[rgt].Y.X);
        nd[ id ].Y.Y=max(nd[lft].Y.Y,nd[rgt].Y.Y);
        nd[ id ].X=min( nd[lft].X,min( nd[rgt].X, nd[rgt].Y.X-nd[lft].Y.Y ) );
    }
}

inline int Far( ) {
    return (nd[1].Y.Y-nd[1].Y.X);
}

inline int Close( ) {
    return nd[1].X;
}

bool Fr[MX+2];
inline void add(int p) {
    int nx=Nd[ p ];
    int vl=ar[ nx ];
    Fr[ nx ]^=1;
    if( Fr[nx]==1 )Ins(1,1,n,vl,1); ///add
    else Ins(1,1,n,vl,0);  ///remove
}

int ans[MX+2];
bool qr[MX+2];
inline void Solve(int q) {
    sq=600;
    sort( v,v+q );
    int cl=v[0].l,cr=cl-1;
    for(int i=0; i<q; i++) {
        int l=v[i].l;
        int r=v[i].r;
        int lc=v[i].lc;
        ///add frm left to l;
        while(cl<l) {
            add(cl++);
        }
        /// add frm rgt to l
        while(cl>l) {
            add(--cl);
        }
        /// add frm lft to r
        while(cr<r) {
            add(++cr);
        }
        /// rmv frm rgt to r
        while(cr>r) {
            add(cr--);
        }
        if( lc!=-1 ) add( St[lc] );
        ///Special case for adding Lca if endpoint is not lca!!
        int idx=v[i].id;
        if( qr[idx] )ans[ idx ]=Close( );
        else ans[ idx ]=Far( );
        if( lc!=-1 ) add( St[lc] );
    }
}
vector<int>vv;
int main() {
    int tc,cs=1,i,j,k,x,y,q;
    S(n);
    fr(i,1,n) {
        S(x);
        ar[i]=x;
        vv.pb( x );
    }
    ///Compressing data
    sort(all(vv));
    vv.resize( unique( all(vv) )-vv.begin() );
    fr(i,1,n) {
        x=lower_bound( all(vv),ar[i] )-vv.begin()+1;
        MP[x]=ar[i];
        ar[i]=x;
    }
    fr(i,1,n-1) {
        S2(x,y);
        G[x].pb(y);
        G[y].pb(x);
    }
    tmm=0;
    SET(P);
    Dfs(1,-1,1);
    Par_Sparse( );
    S(q);
    for(i=1; i<=q; i++) {
        char ch[2];
        scanf("%s",ch);
        S2(x,y);
        if( ch[0]=='C' )qr[i]=1; ///Close
        else qr[i]=0;///Far

        if( St[x]>St[y] )swap( x, y );
        int lc=Lca(x,y);
        if( lc==y ) v[i-1]=data( St[y],St[x],i,-1 );
        else v[i-1]=data( Ed[x],St[y],i,lc );
    }
    for(i=0; i<4*MX; i++) {
        nd[i].X=nd[i].Y.X=inf;
        nd[i].Y.Y=-inf;
    }
    Solve(q);
    fr(i,1,q) {
        printf("%d\n",ans[i]);
    }
    return 0;
}