# HackerEarth Tree queries problem solution

In this HackerEarth Tree queries problem solution You are given a tree T with N nodes rooted at node 1. Each node has a value A[i] associated with it.

You are required to perform Q queries where each query is of type:
1. u x: Increment the value associated with node u by x.
2. p: Find the shortest distance of any node from the root that has a value strictly greater than p. If no such node exists, then print -1.

## HackerEarth Tree queries problem solution.

`#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <queue>#include <ctime>#include <cassert>#include <complex>#include <string>#include <cstring>#include <chrono>#include <random>#include <queue>#include <bitset>#include <iomanip>#include <fstream>#include <stack>using namespace std; typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> PII;typedef pair<ll , ll> PLL;typedef long double ld; #define pb push_back#define all(c) c.begin(),c.end()#define allr(c) c.rbegin(),c.rend()int mod = 1000000007;const int inf = 1034567891;const ll LL_INF = 1234567890123456789ll;#define PI 3.14159265#define endl '\n'#define F first#define S second#define debug(x) cout << #x << " = " << x << endl;#define TRACE #ifdef TRACE#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)template <typename Arg1>void __f(const char* name, Arg1&& arg1){  cout << name << " : " << arg1 << endl;}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}#else#define trace(...)#endif #define out(container) for (auto it : container) cout << it << " "; cout << endl;  template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }template < typename T > string toString(T a)       { return to_string(a); }template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}inline int mul(int x, int y){ return (x * 1ll * y) % mod;}inline int powr(int a, ll b){  int x = 1 % mod;  while(b){    if(b & 1) x = mul(x, a);    a = mul(a, a);    b >>= 1;  }  return x;}inline int inv(int a){ return powr(a, mod - 2);}const int N = 2e5 + 5;ll t[4*N], a[N];void build(int v, int tl, int tr) {  if (tl == tr) {    t[v] = a[tl];  } else {    int tm = (tl + tr) / 2;    build(v*2, tl, tm);    build(v*2+1, tm+1, tr);    t[v] = max(t[v*2], t[v*2+1]);  }}void update(int v, int tl, int tr, int pos, ll new_val) {  if (tl == tr) {    t[v] += new_val;  } else {    int tm = (tl + tr) / 2;    if (pos <= tm)      update(v*2, tl, tm, pos, new_val);    else      update(v*2+1, tm+1, tr, pos, new_val);    t[v] = max(t[v*2], t[v*2+1]);  }}int get_first(int v, int lv, int rv, int l, int r, ll x) {  if(lv > r || rv < l) return -1;  if(l <= lv && rv <= r) {    if(t[v] <= x) return -1;    while(lv != rv) {      int mid = lv + (rv-lv)/2;      if(t[2*v] > x) {        v = 2*v;        rv = mid;      } else {        v = 2*v+1;        lv = mid+1;      }    }    return lv;  }  int mid = lv + (rv-lv)/2;  int rs = get_first(2*v, lv, mid, l, r, x);  if(rs != -1) return rs;  return get_first(2*v+1, mid+1, rv, l ,r, x);}vector<int> adj[N];bool vis[N];int dis[N];void dfs(int s, int d) {  vis[s] = true;  dis[s] = d;  for (auto it : adj[s]) {    if (!vis[it]) {      dfs(it, d + 1);    }  }}int main(){  ios_base::sync_with_stdio(false);  cin.tie(NULL);  int tt;  cin >> tt;  assert(1 <= tt and tt <= 10);  while(tt--){      for(int i = 0 ; i < N ; i++)      {        adj[i].clear();        vis[i] = false;        dis[i] = 0;      }      for(int i = 0 ; i < 4*N ; i++) t[i] = 0;      int n;      cin >> n;      assert(2 <= n and n <= 100000);      ll val[N];      for (int i = 1; i <= n; i++) {        cin >> val[i];        assert(1 <= val[i] and val[i] <= 1000000);      }        ll u, v;      for (int i = 0; i < n - 1; i++) {        cin >> u >> v;        assert(1 <= u and u <= n);        assert(1 <= v and v <= n);        adj[u].pb(v);        adj[v].pb(u);      }      dfs(1, 0);      vector<PLL> vec;      vector<int> pos(n + 1, 0);      for (int i = 1; i <= n; i++) {        vec.pb({dis[i], i});      }      sort(all(vec));      int m = n;      for (int i = 1; i <= m; i++) {        pos[vec[i - 1].S] = i;        a[i] = val[vec[i - 1].S];      }      build(1, 1, m);      int q;      cin >> q;      assert(2 <= q and q <= 100000);      while (q--) {        int type;        cin >> type;        if (type == 1) {          ll x, y;          cin >> x >> y;          assert(1 <= x and x <= n);          assert(1 <= y and y <= 1000000);          update(1, 1, m, pos[x], y);          val[x] += y;          a[pos[x]] += y;        } else {          ll x;          cin >> x;          assert(1 <= x and x <= 1000000000000);          int ind = get_first(1, 1, m, 1, m, x);          if (ind == -1) {            cout << ind << endl;          } else {            v = a[ind];            cout << dis[vec[ind - 1].S] << endl;          }        }      }    }  return 0;}`

### Second solution

`from collections import defaultdictMAXN = int(1e12) + 10class Fenwick:    def __init__(self):        self.f = defaultdict(lambda: MAXN)    def upd(self, p, x):        p = MAXN - p - 1        while p < MAXN:            self.f[p] = min(self.f[p], x)            p += p & -p    def get(self, p):        p = MAXN - p - 1        ans = MAXN        while p > 0:            ans = min(ans, self.f[p])            p ^= p & -p        return anst = int(input())while t > 0:    t -= 1    n = int(input())    a = list(map(int, input().split()))    g = [[] for i in range(n)]    h = [0] * n    for i in range(n - 1):        v, u = map(int, input().split())        v -= 1        u -= 1        g[v] += [u]        g[u] += [v]    fen = Fenwick()    def dfs(v, p):        fen.upd(a[v], h[v])        for u in g[v]:            if p != u:                h[u] = h[v] + 1                dfs(u, v)    dfs(0, -1)    q = int(input())    while q > 0:        q -= 1        query = list(map(int, input().split()))        if query[0] == 1:            query[1] -= 1            a[query[1]] += query[2]            fen.upd(a[query[1]], h[query[1]])        else:            ans = fen.get(query[1] + 1)            print(-1 if ans == MAXN else ans)`