Algorithm


Problem Name: Data Structures - Subtrees And Paths

Problem Link: https://www.hackerrank.com/challenges/subtrees-and-paths/problem?isFullScreen=true

In this HackerRank in Data Structures - Subtrees And Paths solutions,

Given a rooted tree of N nodes, where each node is uniquely numbered in between [1..N]. The node 1 is the root of the tree. Each node has an integer value which is initially 0.

You need to perform the following two kinds of queries on the tree:

 

  • add t value: Add value to all nodes in subtree rooted at t
  • max a b: Report maximum value on the path from a to b

Input Format

First line contains N, number of nodes in the tree. Next N-1 lines contain two space separated integers x and y which denote that there is an edge between node x and node y.
Next line contains Q, the number of queries to process.
Next Q lines follow with either add or max query per line.

Constraints

1 <= N <= 10**5

1 <= Q <= 10**5

1 <= t,a,b,x,y <= N

x not= y

-10**4 <= value <= 10**4

Output Format

For each max query output the answer in a separate line.

Sample Input

5
1 2
2 3
2 4
5 1
6
add 4 30
add 5 20
max 4 5
add 2 -20
max 4 5
max 3 4

Sample Output

30
20
10

Explanation

In the test case we have the following tree:

Initially all node values are zero.
Queries are performed in the following way:

add 4 30 // add 30 to node 4
add 5 20 // add 20 to node 5
max 4 5 // maximum of nodes 4,2,1,5 is 30
add 2 -20 // subtract 20 from nodes 2,3,4
max 4 5 // maximum of nodes 4,2,1,5 is 20
max 3 4 // maximum of nodes 3,2,4 is 10

 

 

 

Code Examples

#1 Code Example with C Programming

Code - 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("%d\n",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;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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
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 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 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 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("%d\n", res);
        }
    }

    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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();
  }
    
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] White Falcon And Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Triplets solution in Hackerrank - Hacerrank solution C, C++, java,js, Python