HackerEarth Strange City problem solution

In this HackerEarth Strange City problem solution Anchal lives in a city which has N ice cream parlours. The city has N - 1 connections such that every ice cream parlour can be reached from every other ice cream parlour. Each parlour has only one type of ice cream with cost Ci for each 1<=i<=N. Anchal has Q queries with each query specifying a city R and two integers X and Y. In every query she wants to reach the same destination ice cream parlour D.Anchal wants to calculate the number of cities from which she can start her journey and reach the destination city D along the shortest path between the source and the destination city such that city R lies in its path and the sum of ice creams for these three cities lie between X and Y (Both inclusive).

 

HackerEarth Strange City problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,q,d,currtime=0;
vector<int> v[100005];
vector<ll> tree[4*100005];
bool vis[100005];
int st[100005],en[100005],val[100005],c[100005];
void build(int n,int l,int r) // Building a merge sort tree
{
    if(l==r){
        tree[n].push_back(c[val[l]]);
        return;
    }
    int mid= (l+r)/2;
    build(2*n,l,mid);
    build(2*n+1,mid+1,r);
    merge(tree[2*n].begin(),tree[2*n].end(),tree[2*n+1].begin(),tree[2*n+1].end(),back_inserter(tree[n]));
}
int query(int n,ll k,int l,int r,int start,int end) // querying number of elements greater than or equal to k in range l to r
{
    //cout<<"run"<<endl;
    if(start>r || end<l)
        return 0;
    if(start>=l && end<=r){
        if(tree[n].size()==0)
        return 0;
        int pos= lower_bound(tree[n].begin(),tree[n].end(),k)-tree[n].begin();
        //cout<<pos<<endl;
        return (tree[n].size()-pos);
    }
    int mid=(start+end)/2;
    int q1= query(2*n,k,l,r,start,mid);
    int q2= query(2*n+1,k,l,r,mid+1,end);
    return (q1+q2);
}
void dfs(int s)
{
    vis[s]=true;
    ++currtime;
    val[currtime]=s;
    st[s]=currtime;
    for(auto i:v[s])
    {
        if(vis[i]==false){
            dfs(i);
        }
    }
    en[s]=currtime;
}
int main()
{
    //freopen("test10.txt","r",stdin);
    //freopen("file10.txt","wb",stdout);
    cin>>n>>d;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    for(int i=1;i<=n-1;i++){
        int so,de;
        cin>>so>>de;
        v[so].push_back(de);
        v[de].push_back(so);
    }
    dfs(d);
    for(int i=1;i<=n;i++){
        //cout<<val[i]<<endl;
    }
    build(1,1,n);
    cin>>q;
    while(q--)
    {
        int r;
        ll x,y;
        cin>>r>>x>>y;
        ll up = y - c[d] - c[r];
        ll lo = x - c[d] - c[r];
        cout<<(query(1,lo,st[r]+1,en[r],1,n)-query(1,up+1,st[r]+1,en[r],1,n))<<endl;
    }
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define MP make_pair
#define ff first
#define ss second
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((vlong)(x).size())
#define LL long long
#define LLU long long unsigned int
typedef long long vlong;
typedef unsigned long long uvlong;

const int Size = 100005;

int N, Q, root, NNODE;
LL C[Size], A[Size];
vector<int> G[Size];
int dis[Size], fin[Size];

struct vert{
    vector<LL> S;
}T[Size*4];

void bt(int c, int s, int e) {
    if (s == e) {
        T[c].S.pb(A[s]);
        return;
    }
    LL L = c*2, R = L+1, M = (s+e)/2;
    bt(L, s, M);
    bt(R, M + 1, e);
    T[c].S.resize(SZ(T[L].S)+SZ(T[R].S));
    merge(ALL(T[L].S), ALL(T[R].S), T[c].S.begin());
}

int qt(int c, int s, int e, int u, int v, LL st, LL ed) {
    if (s > v || e < u) return 0;
    if (s >= u && e <= v) {
        int res = upper_bound(ALL(T[c].S), ed) - lower_bound(ALL(T[c].S), st);
        return res;
    }
    LL L = c*2, R = L+1, M = (s+e)/2;
    int v1 = qt(L, s, M, u, v, st, ed);
    int v2 = qt(R, M + 1, e, u, v, st, ed);
    return v1+v2;
}

void DFS(int u, int p) {
    NNODE++;
    dis[u] = NNODE;
    A[NNODE] = C[u];
    FOR(i,0,SZ(G[u])-1){
        int v = G[u][i];
        if (v != p) {
            DFS(v, u);
        }
    }
    fin[u] = NNODE;
}

void process(){
    FOR(i,1,N) {
        dis[i] = fin[i] = 0;
    }
    NNODE = 0;
    DFS(root, -1);
    bt(1, 1, NNODE);
}

int query(LL st, LL ed, LL u){
    LL curSum = C[root]+C[u];
    st -= curSum;
    ed -= curSum;
    int ans = qt(1, 1, NNODE, dis[u]+1, fin[u], st, ed);
    return ans;
}

int main () {
    scanf("%d %d %d",&N,&Q,&root);
    FOR(i,1,N){
        scanf("%lld",&C[i]);
    }

    FOR(i,1,N-1){
        int u, v;
        scanf("%d %d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
    }

    process();
    LL last = 0;

    FOR(i,1,Q){
        LL IN1, IN2, IN3;
        scanf("%lld %lld %lld",&IN1,&IN2,&IN3);
        LL R = last^IN1;
        LL X = last^IN2;
        LL Y = last^IN3;
        last = query(X, Y, R);
        printf("%lld\n",last);
    }

    return 0;
}