HackerRank Subtrees And Paths problem solution YASH PAL, 31 July 2024 In this HackerRank Subtrees and Paths problem solution, you are given a rooted tree of N nodes. first, we need to add value to all nodes in the subtree rooted at t. and report the maximum value on the path from a to b node. Problem solution in Java Programming. import java.io.*; import java.util.*; public class Solution { static class Node { int to; int next; } static int cnt = 0; static int[] head; static Node[] e; static void insert(int u, int v) { e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } static int[][] fa; static int[] deep; static int[] size; static boolean[] vis; static class NodeDfs1 { int x; int p; boolean start = true; public NodeDfs1(int x, int p) { this.x = x; this.p = p; } } static void dfs1(int x) { Deque<NodeDfs1> deque = new LinkedList<>(); deque.add(new NodeDfs1(x, -1)); while (!deque.isEmpty()) { NodeDfs1 node = deque.pollLast(); size[node.x] = 1; vis[node.x] = true; for (int i = 1; i <= 20; i++) { if (deep[node.x] < (1 << i)) break; fa[node.x][i] = fa[fa[node.x][i - 1]][i - 1]; } for (int i = head[node.x]; i > 0; i = e[i].next) { if (vis[e[i].to]) continue; deep[e[i].to] = deep[node.x] + 1; fa[e[i].to][0] = node.x; deque.add(new NodeDfs1(e[i].to, x)); } if (node.p >= 0) { size[node.p] += size[node.x]; } } } static int sz = 0; static int[] pos; static int[] belong; static int[] endpos; static class NodeDfs2 { int x; int chain; int k = 0; int step = 0; public NodeDfs2(int x, int chain) { this.x = x; this.chain = chain; } } static void dfs2(int x, int chain) { Deque<NodeDfs2> deque = new LinkedList<>(); deque.add(new NodeDfs2(x, chain)); while (!deque.isEmpty()) { NodeDfs2 node = deque.peekLast(); if (node.step == 0) { sz++; pos[node.x] = sz; belong[node.x] = node.chain; for (int i = head[node.x]; i > 0; i = e[i].next) { if (deep[e[i].to] > deep[node.x] && size[e[i].to] > size[node.k]) { node.k = e[i].to; } } if (node.k == 0) { endpos[node.x] = sz; deque.removeLast(); } else { deque.add(new NodeDfs2(node.k, node.chain)); node.step = 1; } } else if (node.step == 1) { for (int i = head[node.x]; i > 0; i = e[i].next) { if (deep[e[i].to] > deep[node.x] && node.k != e[i].to) { deque.add(new NodeDfs2(e[i].to, e[i].to)); } } node.step = 2; } else if (node.step == 2) { endpos[node.x] = sz; deque.removeLast(); } } } static int lca(int x, int y) { if (deep[x] < deep[y]) { int tmp = x; x = y; y = tmp; } int t = deep[x] - deep[y]; for (int i = 0; i <= 20; i++) { if ( (t & (1 << i)) != 0) { x = fa[x][i]; } } for (int i = 20; i >= 0; i--) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return (x == y) ? x : fa[x][0]; } static int[] tree; static int[] lazy; static void update(int node, int a, int b, int i, int j, int value) { if (lazy[node] != 0) { tree[node] += lazy[node]; if (a != b) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } lazy[node] = 0; } if (a > b || a > j || b < i) return; if (a >= i && b <= j) { tree[node] += value; if (a != b) { lazy[node * 2] += value; lazy[node * 2 + 1] += value; } return; } update(node * 2, a, (a + b) / 2, i, j, value); update(1 + node * 2, 1 + (a + b) / 2, b, i, j, value); tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]); } static int queryTree(int node, int a, int b, int i, int j) { if (a > b || a > j || b < i) return Integer.MIN_VALUE; if (lazy[node] != 0) { tree[node] += lazy[node]; if (a != b) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } lazy[node] = 0; } if (a >= i && b <= j) return tree[node]; int q1 = queryTree(node * 2, a, (a + b) / 2, i, j); int q2 = queryTree(1 + node * 2, 1 + (a + b) / 2, b, i, j); int res = Math.max(q1, q2); return res; } static int solvemx(int n, int x, int f) { int mx = Integer.MIN_VALUE; while (belong[x] != belong[f]) { mx = Math.max(mx, queryTree(1, 1, n, pos[belong[x]], pos[x])); x = fa[belong[x]][0]; } mx = Math.max(mx, queryTree(1, 1, n, pos[f], pos[x])); return mx; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); e = new Node[(n+1)*2]; for (int i = 0; i <= n*2; i++) { e[i] = new Node(); } head = new int[n+1]; for (int i = 0; i < n - 1; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); insert(u, v); insert(v, u); } fa = new int[n+1][21]; deep = new int[n+1]; size = new int[n+1]; belong = new int[n+1]; endpos = new int[n+1]; vis = new boolean[n+1]; dfs1(1); pos = new int[n+1]; dfs2(1, 1); tree = new int[n * 4]; lazy = new int[n * 4]; st = new StringTokenizer(br.readLine()); int q = Integer.parseInt(st.nextToken()); for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); String str = st.nextToken(); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); if ("add".equals(str)) { update(1, 1, n, pos[x], endpos[x], y); } else { int t = lca(x, y); bw.write(Math.max(solvemx(n, x, t), solvemx(n, y, t)) + "n"); } } bw.close(); br.close(); } } Problem solution in C++ programming. #include <bits/stdc++.h> using namespace std; #define repu(i, a, b) for (int i = (a); i < (b); ++i) #define repd(i, a, b) for (int i = (a); i > (b); --i) #define mem(a, x) memset(a, x, sizeof(a)) #define all(a) a.begin(), a.end() #define uni(a) a.erase(unique(all(a)), a.end()) #define count_bits(x) __builtin_popcount(x) #define count_bitsll(x) __builtin_popcountll(x) #define least_bits(x) __builtin_ffs(x) #define least_bitsll(x) __builtin_ffsll(x) #define most_bits(x) 32 - __builtin_clz(x) #define most_bitsll(x) 64 - __builtin_clz(x) vector<string> split(const string &s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(x); return v; } #define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); } void err(vector<string>::iterator it) {} template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << 'n'; err(++it, args...); } typedef long long ll; const int MOD = 1000000007; template<class T> inline T tmin(T a, T b) {return (a < b) ? a : b;} template<class T> inline T tmax(T a, T b) {return (a > b) ? a : b;} template<class T> inline void amax(T &a, T b) {if (b > a) a = b;} template<class T> inline void amin(T &a, T b) {if (b < a) a = b;} template<class T> inline T tabs(T a) {return (a > 0) ? a : -a;} template<class T> T gcd(T a, T b) {while (b != 0) {T c = a; a = b; b = c % b;} return a;} #define MAX_LOG 19 #define MAXN 100005 int n; vector<int> G[MAXN]; /* HLD */ int chain_head[MAXN], pos_base[MAXN], chain_index[MAXN], end_sub[MAXN]; int ptr, num_chain; /* LCA */ int par[MAX_LOG][MAXN], depth[MAXN], subtree[MAXN]; /* ST */ struct node { int maxi, lazy; } st[MAXN * 4]; /* LCA */ void dfs(int v, int p, int d) { par[0][v] = p; depth[v] = d; subtree[v] = 1; repu(i, 0, G[v].size()) { if (G[v][i] != p) { dfs(G[v][i], v, d + 1); subtree[v] += subtree[G[v][i]]; } } } void init() { dfs(1, -1, 0); for (int k = 0; k + 1 < MAX_LOG; ++k) { for (int v = 1; v <= n; ++v) { if (par[k][v] < 0) par[k + 1][v] = -1; else par[k + 1][v] = par[k][par[k][v]]; } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < MAX_LOG; ++k) { if ((depth[u] - depth[v]) >> k & 1) { v = par[k][v]; } } if (u == v) return u; for (int k = MAX_LOG - 1; k >= 0; --k) { if (par[k][u] != par[k][v]) { u = par[k][u]; v = par[k][v]; } } return par[0][u]; } /* Segment tree */ inline void lazy_eval(int ind, int len) { if (st[ind].lazy != 0) { st[ind].maxi += st[ind].lazy; if (len > 1) { int c1 = ind << 1, c2 = c1 | 1; st[c1].lazy += st[ind].lazy; st[c2].lazy += st[ind].lazy; } st[ind].lazy = 0; } } void build_tree(int ind, int s, int e) { if(s == e - 1) { st[ind].maxi = st[ind].lazy = 0; return; } int c1 = ind << 1, c2 = c1 | 1, m = (s + e) >> 1; build_tree(c1, s, m); build_tree(c2, m, e); st[ind].maxi = tmax(st[c1].maxi, st[c2].maxi); st[ind].lazy = 0; } void update_tree(int ind, int s, int e, int ss, int ee, int val) { lazy_eval(ind, e - s); if (s >= ee || e <= ss) return; if (s >= ss && e <= ee) { st[ind].lazy += val; lazy_eval(ind, e - s); return; } int c1 = ind << 1, c2 = c1 | 1, m = (s + e) >> 1; update_tree(c1, s, m, ss, ee, val); update_tree(c2, m, e, ss, ee, val); st[ind].maxi = tmax(st[c1].maxi, st[c2].maxi); } int query_tree(int ind, int s, int e, int ss, int ee) { lazy_eval(ind, e - s); if (s >= ee || e <= ss) return INT_MIN; if (s >= ss && e <= ee) return st[ind].maxi; int c1 = ind << 1, c2 = c1 | 1, m = (s + e) >> 1; int vl = query_tree(c1, s, m, ss, ee); int vr = query_tree(c2, m, e, ss, ee); st[ind].maxi = tmax(st[c1].maxi, st[c2].maxi); return tmax(vl, vr); } /* Heavy light decomposition */ void build_hld(int u) { if(chain_head[num_chain] == -1) chain_head[num_chain] = u; chain_index[u] = num_chain; pos_base[u] = ptr++; int most = 0, dem = -1; repu(i, 0, G[u].size()) { int v = G[u][i]; if (v != par[0][u]) { if (subtree[v] > most) { most = subtree[v]; dem = v; } } } if (dem != -1) build_hld(dem); repu(i, 0, G[u].size()) { int v = G[u][i]; if (v != par[0][u] && v != dem) { ++num_chain; build_hld(v); } } end_sub[u] = ptr; } /* query on path u -> v */ int query_hld(int u, int v) { int ans = INT_MIN; int uchain, vchain = chain_index[v]; /* interval [x, y) */ while (1) { uchain = chain_index[u]; if (uchain != vchain) { int tmp = query_tree(1, 0, ptr, pos_base[chain_head[uchain]], pos_base[u] + 1); /* process something here */ amax(ans, tmp); u = chain_head[uchain]; u = par[0][u]; } else { int tmp = query_tree(1, 0, ptr, pos_base[v], pos_base[u] + 1); /* process something here */ amax(ans, tmp); break; } } return ans; } /* update value on path u -> v */ void update_hld(int v, int val) { int s = pos_base[v], e = end_sub[v]; update_tree(1, 0, ptr, s, e, val); } int main(int argc, char *argv[]) { ios_base::sync_with_stdio(false); int q, a, b; string op; mem(chain_head, -1); ptr = num_chain = 0; cin >> n; repu(i, 1, n) { cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } init(); build_hld(1); build_tree(1, 0, n); cin >> q; repu(i, 0, q) { cin >> op >> a >> b; if (op[0] == 'a') update_hld(a, b); else { int p = lca(a, b); int res = query_hld(a, p); amax(res, query_hld(b, p)); printf("%dn", res); } } return 0; } Problem solution in C programming. #include <stdio.h> #include <stdlib.h> #include <string.h> #define INF 1000000007 typedef struct _lnode{ int x; int w; struct _lnode *next; } lnode; typedef struct _tree{ int max; int off; } tree; void insert_edge(int x,int y,int w); void dfs0(int u); void dfs1(int u,int c); void dfs2(int u); void preprocess(); int lca(int a,int b); int sum(int v,int tl,int tr,int l,int r,tree *t); int min(int x,int y); int max(int x,int y); int solve(int x,int ancestor); void range_update (int v, int tl, int tr, int pos1, int pos2, int new_val,tree *t); void push(int v,int tl,int tr,tree *t); void init( int n ); void range_increment( int i, int j, int val ); int query( int i ); char str[10]; int N,NN,cn,level[100000],DP[18][100000],subtree_size[100000],special[100000],node_chain[100000],node_idx[100000],chain_head[100000],chain_len[100000]={0}; int *range_upt,chain_order[100000],node_begin[100000],node_end[100000],con=0; lnode *table[100000]={0}; tree *chain[100000]; int main(){ int Q,x,y,i; scanf("%d",&N); for(i=0;i<N-1;i++){ scanf("%d%d",&x,&y); insert_edge(x-1,y-1,1); } preprocess(); scanf("%d",&Q); while(Q--){ scanf("%s",str); switch(str[0]){ case 'a': scanf("%d%d",&x,&y); range_increment(node_begin[x-1],node_end[x-1],y); if(node_idx[x-1]) range_update(1,0,chain_len[node_chain[x-1]]-1,node_idx[x-1],chain_len[node_chain[x-1]]-1,y,chain[node_chain[x-1]]); break; default: scanf("%d%d",&x,&y); i=lca(x-1,y-1); printf("%dn",max(solve(x-1,i),solve(y-1,i))); } } return 0; } void insert_edge(int x,int y,int w){ lnode *t=malloc(sizeof(lnode)); t->x=y; t->w=w; t->next=table[x]; table[x]=t; t=malloc(sizeof(lnode)); t->x=x; t->w=w; t->next=table[y]; table[y]=t; return; } void dfs0(int u){ lnode *x; subtree_size[u]=1; special[u]=-1; for(x=table[u];x;x=x->next) if(x->x!=DP[0][u]){ DP[0][x->x]=u; level[x->x]=level[u]+1; dfs0(x->x); subtree_size[u]+=subtree_size[x->x]; if(special[u]==-1 || subtree_size[x->x]>subtree_size[special[u]]) special[u]=x->x; } return; } void dfs1(int u,int c){ lnode *x; node_chain[u]=c; node_idx[u]=chain_len[c]++; for(x=table[u];x;x=x->next) if(x->x!=DP[0][u]) if(x->x==special[u]) dfs1(x->x,c); else{ chain_head[cn]=x->x; dfs1(x->x,cn++); } return; } void dfs2(int u){ lnode *x; node_begin[u]=con; if(!node_idx[u]) chain_order[node_chain[u]]=con++; for(x=table[u];x;x=x->next) if(x->x!=DP[0][u]) dfs2(x->x); node_end[u]=con-1; return; } void preprocess(){ int i,j; level[0]=0; DP[0][0]=0; dfs0(0); for(i=1;i<18;i++) for(j=0;j<N;j++) DP[i][j] = DP[i-1][DP[i-1][j]]; cn=1; chain_head[0]=0; dfs1(0,0); for(i=0;i<cn;i++){ chain[i]=(tree*)malloc(4*chain_len[i]*sizeof(tree)); memset(chain[i],0,4*chain_len[i]*sizeof(tree)); } range_upt=malloc(4*cn*sizeof(int)); init(cn); dfs2(0); return; } int lca(int a,int b){ int i; if(level[a]>level[b]){ i=a; a=b; b=i; } int d = level[b]-level[a]; for(i=0;i<18;i++) if(d&(1<<i)) b=DP[i][b]; if(a==b)return a; for(i=17;i>=0;i--) if(DP[i][a]!=DP[i][b]) a=DP[i][a],b=DP[i][b]; return DP[0][a]; } int sum(int v,int tl,int tr,int l,int r,tree *t){ push(v,tl,tr,t); if(l>r) return -INF; if(l==tl && r==tr) return t[v].max; int tm=(tl+tr)/2; return max(sum(v*2,tl,tm,l,min(r,tm),t),sum(v*2+1,tm+1,tr,max(l,tm+1),r,t)); } int min(int x,int y){ return (x<y)?x:y; } int max(int x,int y){ return (x>y)?x:y; } int solve(int x,int ancestor){ int ans=-INF; while(node_chain[x]!=node_chain[ancestor]){ ans=max(ans,sum(1,0,chain_len[node_chain[x]]-1,0,node_idx[x],chain[node_chain[x]])+query(chain_order[node_chain[x]])); x=DP[0][chain_head[node_chain[x]]]; } ans=max(ans,sum(1,0,chain_len[node_chain[x]]-1,node_idx[ancestor],node_idx[x],chain[node_chain[x]])+query(chain_order[node_chain[x]])); return ans; } void range_update (int v, int tl, int tr, int pos1, int pos2, int new_val,tree *t) { push(v,tl,tr,t); if(pos2<tl || pos1>tr) return; if (pos1<=tl && pos2>=tr) t[v].off += new_val; else { int tm = (tl + tr) / 2; range_update (v*2, tl, tm, pos1,pos2, new_val,t); range_update (v*2+1, tm+1, tr, pos1,pos2, new_val,t); push(v*2,tl,tm,t); push(v*2+1,tm+1,tr,t); t[v].max = max(t[v*2].max , t[v*2+1].max); } } void push(int v,int tl,int tr,tree *t){ if(!t[v].off) return; t[v].max+=t[v].off; if(tl!=tr){ t[2*v].off+=t[v].off; t[2*v+1].off+=t[v].off; } t[v].off=0; return; } void init( int n ){ NN = 1; while( NN < n ) NN *= 2; int i; for( i = 1; i < NN + n; i++ ) range_upt[i] = 0; } void range_increment( int i, int j, int val ){ for( i += NN, j += NN; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 ) { if( i % 2 == 1 ) range_upt[i] += val; if( j % 2 == 0 ) range_upt[j] += val; } } int query( int i ){ int ans = 0,j; for( j = i + NN; j; j /= 2 ) ans += range_upt[j]; return ans; } coding problems data structure