## Algorithm

Problem Name: Data Structures - Rooted Tree

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:

1. Update Operation
2. 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 (109 + 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 ≤ 105
1 ≤ E ≤ 105
1 ≤ R, X, Y, T, A, B ≤ N
1 ≤ V, K ≤ 109
X ≠ Y

Sample Input

``````7 7 1
1 2
2 3
2 4
2 5
5 6
6 7
U 5 10 2
U 4 5 3
Q 1 7
U 6 7 4
Q 2 7
Q 1 4
Q 2 4
``````

Sample Output

``````36
54
5
5
``````

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 &

### #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 &

### #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<>();
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;
}
}
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) {
}

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 {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

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++) {
}
for (int i = 0; i  <  n-1; i++) {
int u = Integer.parseInt(st.nextToken())-1;
int v = Integer.parseInt(st.nextToken())-1;
}

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) {
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 &