SPOJ: COT2 (MO'S ALGO)

SPOJ: COT2 (MO'S ALGO)
///==================================================///
///                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 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     200005
#define inf    2000000010
#define MD     1000000007LL
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
int n,Cst[MX+2],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=18; 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 );
    }
};

vector<data>v;
int tot,MP[MX+5];
bool Fr[MX+2];

void add(int p) {
    int nx=Nd[p];
    int vl=Cst[ nx ];
    Fr[ nx ]^=1;
    if( Fr[nx]==1 ){///add;
        MP[vl]++;
        if( MP[vl]==1 )tot++;
    } else { ///remove;
        MP[vl]--;
        if( MP[vl]==0 )tot--;
    }
}

int ans[MX+2];
int main() {
    int tc,cs=1,i,j,k,x,y,q;

    S2(n,q);
    vector<int>vv;
    fr(i,1,n) {
        S(x);
        Cst[i]=x;
        vv.pb(x);
    }
    ///Compressing data
    sort(all(vv));
    fr(i,1,n)Cst[i]=lower_bound( all(vv),Cst[i] )-vv.begin()+1;

    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( );

    for(i=1; i<=q; i++) {
        S2(x,y);
        if( L[x]<L[y] )swap( x, y );
        int lc=Lca(x,y);
        if( lc==y ) {
            v.pb( data( St[y],St[x],i,-1 ) );
        } else {
            if( Ed[x]<St[y] )v.pb( data( Ed[x],St[y],i,lc ) );
            else v.pb( data( Ed[y],St[x],i,lc ) );
        }
    }
    sq=sqrt(n+1);
    sort(all(v));
    CLR( MP );
    CLR( Fr );
    int cl=v[0].l,cr=cl-1;
    tot=0;
    for(int i=0; i<q; i++) {
        int l=v[i].l;
        int r=v[i].r;
        int lc=v[i].lc;
        ///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!!
        ans[ v[i].id ]=tot;
        if( lc!=-1 ) add( St[lc] );
    }
    fr(i,1,q) {
        printf("%d\n",ans[i]);
    }
    return 0;
}