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