[Solved] Rooted Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Algorithm

Problem Name: Data Structures - Rooted Tree

Problem Link: https://www.hackerrank.com/challenges/rooted-tree/problem?isFullScreen=true

In this HackerRank in Data Structures - Rooted Tree solutions,

You are given a rooted tree with N nodes and the root of the tree, R, is also given. Each node of the tree contains a value, that is initially empty. You have to mantain the tree under two operations:

Update Operation
Report Operation

Update Operation
Each Update Operation begins with the character U. Character U is followed by 3 integers T, V and K. For every node which is the descendent of the node T, update it's value by adding V + d*K, where V and K are the parameters of the query and d is the distance of the node from T. Note that V is added to node T.

Report Operation
Each Report Operation begins with the character Q. Character Q is followed by 2 integers, A and B. Output the sum of values of nodes in the path from A to B modulo (10⁹ + 7)

Input Format
The first Line consists of 3 space separated integers, N E R, where N is the number of nodes present, E is the total number of queries (update + report), and R is root of the tree.

Each of the next N-1 lines contains 2 space separated integers, X and Y (X and Y are connected by an edge).

Thereafter, E lines follows: each line can represent either the Update Operation or the Report Operation.

Update Operation is of the form : U T V K.
Report Operation is of the form : Q A B.

Output Format
Output the answer for every given report operation.

Constraints

1 ≤ N, E ≤ 10⁵
1 ≤ E ≤ 10⁵
1 ≤ R, X, Y, T, A, B ≤ N
1 ≤ V, K ≤ 10⁹
X ≠ Y

Sample Input

Sample Output

Explanation

Values of Nodes after U 5 10 2: [0 0 0 0 10 12 14].
Values of Nodes after U 4 5 3: [0 0 0 5 10 12 14].
Sum of the Nodes from 1 to 7: 0 + 0 + 10 + 12 + 14 = 36.
Values of Nodes after U 6 7 4: [0 0 0 5 10 19 25].
Sum of the Nodes from 2 to 7: 0 + 10 + 19 + 25 = 54.
Sum of the Nodes from 1 to 4: 0 + 0 + 5 = 5.
Sum of the Nodes from 2 to 4: 0 + 5 = 5.

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>
#define prime 1000000007L
#define uprime 1000000007U
#define ulprime 1000000007UL

static inline long mod(long self) {
    return (self % prime) + ((self >> 63) & prime);
}

void descending_order(unsigned *self, unsigned *weights, unsigned length) {
    unsigned
        at,
        root = length >> 1,
        member;

    for (self--; root; self[at >> 1] = member) {
        member = self[root];

        for (at = root-- << 1; at  < = length; at <<= 1) {
            at |= (at  <  length) && weights[self[at | 1]] < weights[self[at]];
            if (weights[member] <= weights[self[at]])
                break ;

            self[at >> 1] = self[at];
        }
    }

    for (; length > 1; self[at >> 1] = member) {
        member = self[length];
        self[length--] = self[1];

        for (at = 2; at  < = length; at <<= 1) {
            at |= (at  <  length) && (weights[self[at | 1]] < weights[self[at]]);
            if (weights[member] <= weights[self[at]])
                break ;

            self[at >> 1] = self[at];
        }
    }
}

long point_query(
    unsigned vertex_cnt,
    unsigned sums[vertex_cnt][3],
    int *depths,
    unsigned at
) {
    unsigned
        totals[3] = {0, 0, 0},
        node = at;

    for (; node  <  vertex_cnt; node = (node & (node + 1U)) - 1U) {
        ((unsigned long *)totals)[0] += ((unsigned long *)(sums[node]))[0];
        totals[0] %= uprime;
        totals[1] %= uprime;
        totals[2] = (totals[2] + sums[node][2]) % uprime;
    }

    long total = ((unsigned long)depths[(long)(int)at] * depths[(long)(int)at] * totals[0]) % ulprime;
    total = (total + ((unsigned long)depths[(long)(int)at] * totals[1])) % ulprime;

    return (mod(total - (long)totals[2]) * 500000004UL) % ulprime;
}

int main() {
    unsigned vertex_cnt, operation_cnt, root;
    scanf("%u %u %u", &vertex_cnt, &operation_cnt, &root);

    unsigned
        at = vertex_cnt,
        others,
        ancestors[vertex_cnt];
    {
        unsigned next, ancestor, descendant;
        for (memset(ancestors, 0xFFU, sizeof(ancestors)); --at; ancestors[descendant] = ancestor) {
            scanf("%u %u", &ancestor, &descendant);

            --ancestor;
            if (ancestors[--descendant] != 0xFFFFFFFFU) {
                ancestor   ^= descendant;
                descendant ^= ancestor;
                ancestor   ^= descendant;
            }
            if (ancestors[descendant] != 0xFFFFFFFFU) {
                for (others = descendant; ancestor != 0xFFFFFFFFU; ancestor = next) {
                    next = ancestors[ancestor];
                    ancestors[ancestor] = others;
                    others = ancestor;
                }
                for (; ancestors[descendant] != 0xFFFFFFFFU; ancestor = next) {
                    next = ancestors[descendant];
                    ancestors[descendant] = ancestor;
                    ancestor = descendant;
                }
            }
        }
        ancestor = 0xFFFFFFFFU;
        for (at = --root; at != 0xFFFFFFFFU; at = next) {
            next = ancestors[at];
            ancestors[at] = ancestor;
            ancestor = at;
        }
    }

    unsigned
        weights[vertex_cnt],
        ids[vertex_cnt],
        bases[vertex_cnt],
        base_cnt = 1;
    {
        unsigned
            indices[vertex_cnt + 1],
            descendants[vertex_cnt - 1];

        ancestors[root] = root;
        memset(indices, 0, sizeof(indices));
        for (at = vertex_cnt; at--; indices[ancestors[at]]++);
        for (indices[root]--; ++at  <  vertex_cnt; indices[at + 1] += indices[at]);
        for (indices[at] = at - 1; --at > root; descendants[--indices[ancestors[at]]] = at);
        for (; at--; descendants[--indices[ancestors[at]]] = at);

        unsigned history[vertex_cnt];

        memset(weights, 0, sizeof(weights));
        history[0] = root;
        for (at = 1; at--; )
            if (weights[history[at]])
                for (others = indices[history[at]];
                     others  <  indices[history[at] + 1];
                     weights[history[at]] += weights[descendants[others++]]);
            else {
                weights[history[at]] = 1;
                memcpy(
                    &history[at + 1],
                    &descendants[indices[history[at]]],
                    sizeof(history[0]) * (indices[history[at] + 1] - indices[history[at]])
                );
                at += 1 + (indices[history[at] + 1] - indices[history[at]]);
            }

        unsigned orig_weights[vertex_cnt];
        memcpy(orig_weights, weights, sizeof(weights));

        bases[(ids[root] = 0)] = 0;
        weights[0] = vertex_cnt;
        for (at = 1; at--; ) {
            others = history[at];
            descending_order(
                memcpy(
                    &history[at],
                    &descendants[indices[others]],
                    sizeof(history[0]) * (indices[others + 1] - indices[others])
                ),
                orig_weights,
                (indices[others + 1] - indices[others])
            );

            root = ids[others];
            others = at + (indices[others + 1] - indices[others]);

            unsigned
                base = bases[root],
                id = root + 1;

            for (base_cnt += (others - at) - (at  <  others); at < others; base = (id += weights[id])) {
                ids[history[at]] = id;

                ancestors[id] = root;
                bases[id] = base;
                weights[id] = orig_weights[history[at++]];
            }
        }
    }

    int
        buffers[vertex_cnt + 1],
        *depths = &buffers[1];

    ancestors[0] = 0;
    for (((unsigned long *)buffers)[0] = 0; ++at  <  vertex_cnt; depths[at] = depths[ancestors[at]] + 1);

    unsigned base_ids[vertex_cnt];
    unsigned char
        base_depths[base_cnt],
        max_depth = 0;

    base_depths[0] = 0;
    for (base_ids[(at = 0)] = 0; ++at  <  vertex_cnt; ) {
        base_ids[at] = base_ids[at - 1];

        if (bases[at] != bases[at - 1]) {
            base_depths[++base_ids[at]] = base_depths[base_ids[ancestors[bases[at]]]] + (unsigned char)1;

            if (max_depth  <  base_depths[base_ids[at]])
                max_depth = base_depths[base_ids[at]];
        }
    }

    unsigned ancestral_bases[base_cnt][max_depth];
    memset(ancestral_bases[0], 0, sizeof(ancestral_bases[0]));
    for (at = 0; ++at  <  vertex_cnt; ancestral_bases[base_ids[at]][0] = ancestors[bases[at]]);

    for (others = 0; (others + 1)  <  max_depth; others++)
        for (at = 0; ++at  <  base_cnt; ancestral_bases[at][others + 1] = ancestors[bases[ancestral_bases[at][others]]]);

    unsigned sums[vertex_cnt][3];
    memset(sums, 0, sizeof(sums));

    ancestors[0] = 0xFFFFFFFFU;
    for (getchar(); operation_cnt--; getchar())
        if (getchar() == 'U') {
            scanf(" %u %u %u", &root, &at, &others);
            root = ids[root - 1];

            unsigned coefs[4] = {
                [0] = others,
                [1] = (unsigned) mod((long)(at << 1) - mod((long)others * ((depths[root] << 1) - 1L))),
                [2] = (unsigned) mod((depths[root] - 1L) * mod((long)(at << 1) - mod((long)others * depths[root])))
            };
            for (at = root; at  <  (root + weights[root]); at |= at + 1U) {
                ((unsigned long *)(sums[at]))[0] += ((unsigned long *)coefs)[0];

                sums[at][0] %= uprime;
                sums[at][1] %= uprime;
                sums[at][2] = (sums[at][2] + coefs[2]) % uprime;
            }

            ((unsigned long *) coefs)[0] = ((ulprime << 32) | ulprime) - ((unsigned long *) coefs)[0];
            ((unsigned long *) coefs)[1] = ((ulprime << 32) | ulprime) - ((unsigned long *) coefs)[1];
            coefs[0] %= uprime;
            coefs[1] %= uprime;
            coefs[2] %= uprime;

            if (at > vertex_cnt)
                at = vertex_cnt;

            for (others = root + weights[root]; others  <  at; others |= others + 1U) {
                ((unsigned long *)(sums[others]))[0] += ((unsigned long *)coefs)[0];

                sums[others][0] %= uprime;
                sums[others][1] %= uprime;
                sums[others][2] = (sums[others][2] + coefs[2]) % uprime;
            }
        } else {
            scanf(" %u %u", &at, &others);
            at = ids[at - 1];
            others = ids[others - 1];

            if (others  <  at) {
                at ^= others;
                others ^= at;
                at ^= others;
            }

            if (others  <  (at + weights[at]))
                root = at;
            else {
                unsigned *members = ancestral_bases[base_ids[others]];
                unsigned char dist = base_depths[base_ids[others]];
                for (; dist > 1; dist >>= 1)
                    if (members[dist >> 1] > at) {
                        members += (dist >> 1);
                        dist += dist & 1U;
                    }
                root = members[members[0] > at];
            }

            printf(
                "%lu\n",
                (
                    mod(
                        point_query(vertex_cnt, sums, depths, at)
                      - point_query(vertex_cnt, sums, depths, root)
                    )
                  + mod(
                        point_query(vertex_cnt, sums, depths, others)
                      - point_query(vertex_cnt, sums, depths, ancestors[root])
                    )
                ) % ulprime
            );
        }

    return 0;
}

Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i  <  b; i++)
#define S(x) scanf("%d",&x)
#define P(x) printf("%d\n",x)
typedef long long int LL;

const int mod = 1000000007;
const int MAXN = 100005;
vector<int> g[MAXN];
int dep[MAXN];
int P[MAXN];
int _tm;
int tin[2 * MAXN];
int tout[2 * MAXN];
int n;
int L[MAXN][25];
LL bit1[2 * MAXN], bit2[2 * MAXN], bit3[2 * MAXN];

LL _pow(LL a, LL b){
    if(!b) return 1;
    if(b == 1) return a;
    if(b == 2) return (a * a) % mod;
    if(b & 1) return (a * _pow(a, b - 1)) % mod;
    return _pow(_pow(a, b / 2), 2);
}

void dfs(int c, int p, int d){
    P[c] = p;
    dep[c] = d;
    _tm++;
    tin[c] = _tm;
    rep(i, 0, g[c].size()){
        int u = g[c][i];
        if(u != p) dfs(u, c, d + 1);
    }
    _tm++;
    tout[c] = _tm;
}

void processLca(){
    int i, j;
  //we initialize every element in P with -1
    int N = n;
      for(i = 0; i < n; i++)
          for(j = 0; 1 << j  <  N; j++)
              L[i][j] = -1; 
  //the first ancestor of every node i is T[i]
      for(i = 0; i  <  N; i++)
          L[i][0] = P[i];
  //bottom up dynamic programing
      for(j = 1; 1 << j  <  N; j++)
         for(i = 0; i  <  N; i++)
             if (L[i][j - 1] != -1)
                 L[i][j] = L[L[i][j - 1]][j - 1];
}

int lca(int p, int q){
      int tmp, log, i;
  //if p is situated on a higher level than q then we swap them
      if (dep[p]  <  dep[q])
          tmp = p, p = q, q = tmp;
  //we compute the value of [log(L[p)]
      for(log = 1; 1 << log  < = dep[p]; log++>;
      log--;
  //we find the ancestor of node p situated on the same level
  //with q using the values in P
      for(i = log; i >= 0; i--)
          if (dep[p] - (1 << i) >= dep[q])
              p = L[p][i];
      if (p == q)
          return p;
  //we compute LCA(p, q) using the values in P
      for(i = log; i >= 0; i--)
          if (L[p][i] != -1 && L[p][i] != L[q][i])
              p = L[p][i], q = L[q][i];
      return P[p];
}

void update(LL *bit, int idx, LL val){
    for(int i = idx; i  < = _tm; i += i & -i) bit[i] += val;
}

LL query(LL *bit, int idx){
    LL res = 0;
    for(int i = idx; i; i -= i & -i){
        res += bit[i];
    }
    return res % mod;
}

LL QQQ(int x){
    LL res;
    LL c = dep[x];
    res = (query(bit1, tin[x]) * c) % mod;
    res += (query(bit2, tin[x]) * (((LL)c * c)%mod));
    res %= mod;
    res += query(bit3, tin[x]);
    return res % mod;
}

int main(){
    int e, r;
    scanf("%d%d%d", &n, &e, &r);
    r--;
    rep(i, 0, n - 1){
        int x, y;
        scanf("%d%d", &x, &y);
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(r,-1,0);
    processLca();
    while(e--){
        char s[5];
        scanf("%s", s);
        if(s[0] == 'U'){
            int T, V, K;
            scanf("%d%d%d", &T, &V, &K);
            T--;
            LL k = ((LL)K * _pow(2, mod - 2)) % mod;
            LL p = dep[T];
            LL val;
            val = (V - 2 * p * k + k) % mod;
            val = (val + mod) % mod;
            update(bit1, tin[T], val);
            update(bit1, tout[T] + 1, -val);
            val = k;
            update(bit2, tin[T], val);
            update(bit2, tout[T] + 1, -val);
            val = (p * p) % mod;
            val = (val * k) % mod;
            val -= p * (V + k);
            val %= mod;
            val += mod + V;
            val %= mod;
            update(bit3, tin[T], val);
            update(bit3, tout[T] + 1, -val);
        } else {
            int A, B;
            scanf("%d%d", &A, &B);
            A--; B--;
            LL ans = 0;
            int l = lca(A, B);
            ans = QQQ(A) + QQQ(B) - QQQ(l);
            if(P[l] != -1) ans -= QQQ(P[l]);
            ans %= mod;
            ans += mod;
            ans %= mod;
            printf("%lld\n", ans);
        }
    }
    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 final int D = 17;
  static final int MOD = 1_000_000_007;
  static List < Integer>[] e;
  static int[][] par;
  static int[][] fenwick;
  static int[] dep;
  static int[] dfnl;
  static int[] dfnr;
  static int tick = 0;
  

  static int lowestCommonAncestor(int u, int v) {
    if (dep[u]  <  dep[v]) {
      int temp = u;
      u = v;
      v = temp;
    }
    for (int i = D; --i >= 0; ) {
      if (dep[u]-(1<<i) >= dep[v]) {
        u = par[i][u];
      }
    }
    if (u == v) {
      return u;
    }
    for (int i = D; --i >= 0; ) {
      if (par[i][u] != par[i][v]) {
        u = par[i][u];
        v = par[i][v];
      }
    }
    return par[0][u];
  }
  
  static class Node {
    int u;
    int p;
    boolean start = true;
    Node(int u, int p) {
      this.u = u;
      this.p = p;
    }
  }
  
  static void dfs(int u, int p) {
    Deque < Node> queue = new LinkedList<>();
    queue.add(new Node(u, p));
    while (!queue.isEmpty()) {
      Node node = queue.peek();
      if (node.start) {
        dfnl[node.u] = tick++;
        for (int v: e[node.u]) {
          if (v != node.p) {
            par[0][v] = node.u;
            dep[v] = dep[node.u]+1;
            queue.addFirst(new Node(v, node.u));
          }
        }
        node.start = false;
      } else {
        dfnr[node.u] = tick;
        queue.remove();
      }
    }
  }

  static void add(int fenwick[], int x, int v) {
    for (; x  <  fenwick.length; x |= x+1) {
      fenwick[x] = (fenwick[x] + v) % MOD;
    }
  }

  static int getSum(int fenwick[], int x) {
    int s = 0;
    for (; x > 0; x &= x-1)
      s = (s + fenwick[x-1]) % MOD;
    return s;
  }

  static int get(int u) {
    long pw = 1;
    long s = 0;
    for (int i = 0; i  <  3; i++) {
      s = (s + pw * getSum(fenwick[i], dfnl[u]+1)) % MOD;
      pw = (pw * dep[u]) % MOD;
    }
    return (int) (((MOD+1l) / 2 * s)%MOD);
  }


  static int query(int u, int v) {
    int w = lowestCommonAncestor(u, v);
    long s = ((long)(get(u))+get(v)-get(w))%MOD;
    if (par[0][w] >= 0) {
      s = (s - get(par[0][w])) % MOD;
    }
    return (int) s;
  }

  static void upd(int fenwick[], int l, int r, int v) {
    add(fenwick, l, v);
    add(fenwick, r, -v);
  }

  static void update(int u, int x, int y) {
    int l = dfnl[u];
    int r = dfnr[u];
    upd(fenwick[2], l, r, y);
    upd(fenwick[1], l, r, (int)(((long)(1 - 2 * dep[u]) * y + 2l * x) % MOD));
    upd(fenwick[0], l, r, (int)((dep[u] * (dep[u] - 1l) * y + 2 * (1l - dep[u]) * x) % MOD));
  }
  
  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());
    int m = Integer.parseInt(st.nextToken());
    int rt = Integer.parseInt(st.nextToken())-1;

    
    e = new List[n];
    for (int i = 0; i  <  n; i++) {
      e[i] = new LinkedList<>();
    }
    for (int i = 0; i  <  n-1; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken())-1;
      int v = Integer.parseInt(st.nextToken())-1;
      e[u].add(v);
      e[v].add(u);
    }

    dep = new int[n];
    par = new int[D][n];
    dfnl = new int[n];
    dfnr = new int[n];

    tick = 0;
    dep[rt] = 0;
    par[0][rt] = -1;
    dfs(rt, -1);

    for (int k = 1; k  <  D; k++) {
      for (int i = 0; i  <  n; i++) {
        par[k][i] = par[k-1][i] == -1 ? par[k-1][i] : par[k-1][par[k-1][i]];
      }
    }

    fenwick = new int[3][n];
        
    while (m-- > 0) {
      st = new StringTokenizer(br.readLine());
      char op = st.nextToken().charAt(0);
      int u = Integer.parseInt(st.nextToken()) - 1;
      int v = Integer.parseInt(st.nextToken());
      if (op == 'Q') {
        v--;
        int result = (query(u, v)+MOD)%MOD;
        bw.write(result + "\n");
      } else {
        int w = Integer.parseInt(st.nextToken());
        update(u, v, w);
      }
    }
    
    bw.newLine();
    bw.close();
    br.close();
  }
}

Copy The Code & Try With Live Editor

Demonstration

Previous
[Solved] Dynamic Summation solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Next
[Solved] The crazy helix solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Try With Live Editor

Category - Hacker Rank Online Judge Maniruzzaman Akash 1 year ago 284 0