# HackerEarth Beautiful pair of nodes problem solution

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.

`#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; typedeftree<  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());    }}`