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:
- u x: Increment the value associated with node u by x.
- 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 defaultdict
MAXN = int(1e12) + 10
class 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 ans
t = 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)
0 Comments