HackerEarth Beautiful pair of nodes problem solution

import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class beautiful_nodes
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
    static Random rnd=new Random();
    static int[] x,y,cnt;
    static Pair[] a;
    static int[][] al;
    static int time=-1;
    static int[] c,tin,tout,arr;
    static int maxn=(int)(1e5+5);
    static int[][] bit;
    static int block=3;
    static int[] start,end,idx;
    
    static void dfs(int u,int p)
    {
        tin[u]=++time;arr[time]=-1;
        
        for(int x:al[u])
        {
            if(x!=p)
            {
                dfs(x,u);
            }
        }
        
        tout[u]=time;
    }
    
    static void shuffle(int[] a)
    {
        for(int i=0;i<a.length;i++)
        {
            int next=rnd.nextInt(a.length);
            
            int temp=a[i];a[i]=a[next];a[next]=temp;
        }
    }
    
    static void update(int curr_idx,int val)
    {
        update(idx[curr_idx],val,1);
        
        arr[curr_idx]=val;
    }
    
    static long query(int l,int r,int val)
    {
        long ret=0;
        
        for(int i=idx[l]+1;i<idx[r];i++)
        {
            ret=ret+query(i,val+1);
        }
        
        for(int i=l;i<=Math.min(end[idx[l]],r);i++)
        {
            ret=ret+(arr[i]>val?1:0);
        }
        
        if(idx[l]!=idx[r])
        {
            for(int i=start[idx[r]];i<=r;i++)
            {
                ret=ret+(arr[i]>val?1:0);
            }
        }
        
        return ret;
    }
    
    static void update(int idx1,int idx2,int val)
    {
        while(idx2>0)
        {
            bit[idx1][idx2]+=val;idx2-=idx2&-idx2;
        }
    }
    
    static int query(int idx1,int idx2)
    {
        int ret=0;
        
        while(idx2<maxn)
        {
            ret=ret+bit[idx1][idx2];idx2+=idx2&-idx2;
        }
        
        return ret;
    }
    
    public static void run() throws Exception
    {
        int n=sc.nextInt();
        
        x=new int[n];y=new int[n];cnt=new int[n];
        
        for(int i=1;i<n;i++)
        {
            x[i]=sc.nextInt()-1;y[i]=sc.nextInt()-1;
            
            cnt[x[i]]++;cnt[y[i]]++;
        }
        
        al=new int[n][];
        
        for(int i=0;i<n;i++)
        {
            al[i]=new int[cnt[i]];cnt[i]=0;
        }
        
        for(int i=1;i<n;i++)
        {
            int u=x[i],v=y[i];
            
            al[u][cnt[u]++]=v;al[v][cnt[v]++]=u;
        }
        
        a=new Pair[n];c=new int[n];
        
        for(int i=0;i<n;i++)
        {
            a[i]=new Pair(i,sc.nextInt(),-1);
        }
        
        for(int i=0;i<n;i++)
        {
            a[i].b=sc.nextInt();
            
            c[i]=a[i].b;
        }
        
        shuffle(c);Arrays.sort(c);
        
        for(int i=0;i<n;i++)
        {
            a[i].b=Arrays.binarySearch(c,a[i].b)+1;
        }
        
        tin=new int[n];tout=new int[n];arr=new int[n];dfs(0,-1);
        
        start=new int[block];end=new int[block];idx=new int[n];bit=new int[block][maxn];
        
        for(int i=0,j=0;i<n;i+=block,j++)
        {
            start[j]=i;end[j]=Math.min(n-1,i+block-1);
            
            for(int k=start[j];k<=end[j];k++)
            {
                idx[k]=j;
            }
        }
        
        Arrays.sort(a);int j=0;long res=0;
        
    //  out.println(Arrays.toString(tin)+" "+Arrays.toString(tout)+" "+Arrays.toString(arr));
        
        for(int i=0;i<n;i++)
        {
            while(j<i && a[j].a>a[i].a)
            {
                update(tin[a[j].idx],a[j].b);j++;
            }
            
            long curr=query(tin[a[i].idx],tout[a[i].idx],a[i].b);
            
            res=res+curr;
            
        //  out.println((a[i].idx+1)+" "+curr);
        }
        
        out.println(res);out.close();
    }
    
    private static class Pair implements Comparable<Pair>
    {
        int idx,a,b;
        
        public Pair(int idx,int a,int b)
        {
            this.idx=idx;this.a=a;this.b=b;
        }
        
        public int compareTo(Pair x)
        {
            return -(Integer.compare(this.a,x.a));
        }
    }
    
    public static void main(String[] args) throws Exception
    {
        new Thread(null,new Runnable(){
            public void run()
            {
                try
                {
                    new beautiful_nodes().run();
                }
                catch(Exception e)
                {
                    
                }
            }
        },"1",1<<26).start();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
    
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
    
    public String next() throws Exception {
        return nextToken().toString();
    }
    
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}