In this HackerEarth Beautiful pair of nodes problem solution You are given a rooted tree having n nodes, rooted at node 1. Every node i has two values associated with itself , A[i] and B[i]. In this tree you have to count total pairs of nodes which are beautiful. A pair of nodes i , j is beautiful if i is ancestor of node j and A[i] < A[j] and B[i] < B[j].
Node i is called an ancestor of some node j, if node i is the parent of node j, or it is the ancestor of parent of node j. The root of a tree has no ancestors.


HackerEarth Beautiful pair of nodes problem solution


HackerEarth Beautiful pair of nodes problem solution.

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define LL long long int 
using namespace __gnu_pbds;
using namespace std;
 
typedef
tree<
  pair<int,int>,
  null_type,
  less<pair<int,int>>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
 
vector<int> graph[2000001];
set<int> temp;
bool visit[2000001];
int idx = 0;
int a[2000001];
int b[2000001];
LL final_ans = 0;
 
 
unordered_map<int,int> m;
 
 
ordered_set BIT[200001];
 
void remove(int pos, int val,int node)
    {
        while(pos <= 200000)
            {
                BIT[pos].erase(make_pair(val , node));
                pos += (pos & (-pos));
            }   
    }
 
void add(int pos,int val,int node)
    {
        while(pos <= 200000)
            {
                BIT[pos].insert(make_pair(val , node));
                pos += (pos & (-pos));
            }
    }
 
void query(int pos,int val)
    {
 
        while(pos > 0)
            {
                final_ans = final_ans + (LL)(BIT[pos].order_of_key(make_pair(val , 0)));
                pos -= (pos & (-pos));
            }
    }
 
void dfs(int node)
    {
        ++idx;
        query(m[a[node]]-1 , m[b[node]]);   
        add(m[a[node]] , m[b[node]] , node);
        visit[node] = 1;
        for(int i = 0 ; i < graph[node].size() ; i++)   
            {
                if(visit[graph[node][i]] == 0)
                    {   
                        visit[graph[node][i]] = 1;
                        dfs(graph[node][i]);
                    }
            }
        remove(m[a[node]] , m[b[node]] , node);
        --idx;
    }
 
#define s(x) scanf("%d",&x)
 
int main()
    {
        ios_base::sync_with_stdio(0);
        int n;
        s(n);
        for(int i = 1 ; i <= n - 1 ; i++)
            {
                int u , v;
                s(u);
                s(v);
                graph[u].push_back(v);
                graph[v].push_back(u);
            }
        for(int i = 1 ; i <= n ; i++)
            {
                s(a[i]);
                temp.insert(a[i]);
            }
        for(int i = 1 ; i <= n ; i++)
            {
                s(b[i]);
                temp.insert(b[i]);
            }
        int idxs = 0;
        for(int i : temp)
            {
                m[i] = ++idxs;
            }
        temp.clear();
        dfs(1);
        printf("%lld",final_ans);
    }

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