## Algorithm

Problem Name: Data Structures - Recalling Early Days GP with Trees

In this HackerRank in Data Structures - Recalling Early Days GP with Trees solutions,

You are given a tree with N nodes and each has a value associated with it. You are given Q queries, each of which is either an update or a retrieval operation.

The update query is of the format

``````i j X
``````

This means you'd have to add a GP series to the nodes which lie in the path from node `i` to node `j` (both inclusive) with first term of the GP as `X` on node `i` and the common ratio as `R` (given in the input)

The retrieval query is of the format

i j

You need to return the sum of the node values (S) lying in the path from node i to node j modulo 100711433.

Input Format
The first line contains two integers (N and R respectively) separated by a space.
In the next N-1 lines, the ith line describes the ith edge: a line with two integers a b separated by a single space denotes an edge between a, b.
The next line contains 2 space separated integers (U and Q respectively) representing the number of Update and Query operations to follow.
U lines follow. Each of the next U lines contains 3 space separated integers (i,j, and X respectively).
Each of the next Q lines contains 2 space separated integers, i and j respectively.

Output Format
It contains exactly Q lines and each line containing the answer of the ith query.

Constraints

2 <= N <= 100000
2 <= R <= 109
1 <= U <= 100000
1 <= Q <= 100000
1 <= X <= 10
1 <= a, b, i, j <= N

Sample Input

``````6 2
1 2
1 4
2 6
4 5
4 3
2 2
1 6 3
5 3 5
6 4
5 1
``````

Sample Output

``````31
18
``````

Explanation

The node values after the first updation becomes :

``````3 6 0 0 0 12
``````

The node values after second updation becomes :

``````3 6 20 10 5 12
``````

Answer to Query #1: 12 + 6 + 3 + 10 = 31
Answer to Query #2: 5 + 10 +3 = 18

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MOD 100711433
typedef struct _lnode
{
int x;
int w;
struct _lnode *next;
}lnode;
typedef struct _tree
{
long long sum;
long long offset1;
long long offset2;
}tree;
int N, cn, level[100000], DP[18][100000], subtree_size[100000], special[100000], node_chain[100000], node_idx[100000], chain_head[100000], chain_len[100000] = {0};
long long p[100001], sp[100001];
lnode *table[100000] = {0};
tree *chain[100000];
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
{
dfs1(x -> x, cn++);
}
}
}
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;
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));
}
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];
}
long long sum(int v, int tl, int tr, int l, int r, tree *t)
{
push(v, tl, tr, t);
if( l > r )
{
return 0;
}
if( l == tl && r == tr )
{
return t[v].sum;
}
int tm = ( tl + tr ) / 2;
return ( sum(v*2, tl, tm, l, min(r, tm), t) + sum(v*2+1, tm+1, tr, max(l, tm+1), r, t) ) % MOD;
}
void range_update(int v, int tl, int tr, int pos1, int pos2, long long o1, long long o2, tree *t)
{
push(v, tl, tr, t);
if( pos2  <  tl || pos1 > tr )
{
return;
}
int tm = ( tl + tr ) / 2;
if( pos1  < = tl && pos2 >= tr )
{
t[v].offset1 = o1 * p[tl-pos1] % MOD;
t[v].offset2 = o2 * p[pos2-tr] % MOD;
}
else
{
range_update(v*2, tl, tm, pos1, pos2, o1, o2, t);
range_update(v*2+1, tm+1, tr, pos1, pos2, o1, o2, t);
push(v*2, tl, tm, t);
push(v*2+1, tm+1, tr, t);
t[v].sum = ( t[v*2].sum + t[v*2+1].sum ) % MOD;
}
return;
}
void push(int v, int tl, int tr, tree *t)
{
if( !t[v].offset1 && !t[v].offset2 )
{
return;
}
t[v].sum = ( t[v].sum + ( t[v].offset1 + t[v].offset2 ) * sp[tr-tl] ) % MOD;
if( tl != tr )
{
int tm = ( tl + tr ) / 2;
t[v*2].offset1 = ( t[v*2].offset1 + t[v].offset1 ) % MOD;
t[v*2+1].offset1 = ( t[v*2+1].offset1 + t[v].offset1 * p[tm-tl+1] ) % MOD;
t[v*2].offset2 = ( t[v*2].offset2 + t[v].offset2 * p[tr-tm] ) % MOD;
t[v*2+1].offset2 = ( t[v*2+1].offset2 + t[v].offset2 ) % MOD;
}
t[v].offset1 = t[v].offset2 = 0;
return;
}
void range_solve(int x, int y, long long z)
{
int ca = lca(x, y), ty = y;
long long cac = z % MOD, cay = 0;
while( node_chain[x] != node_chain[ca] )
{
range_update(1, 0, chain_len[node_chain[x]]-1, 0, node_idx[x], 0, cac, chain[node_chain[x]]);
cac = cac * p[node_idx[x]+1] % MOD;
}
range_update(1, 0, chain_len[node_chain[x]]-1, node_idx[ca], node_idx[x], 0, cac, chain[node_chain[x]]);
cac = cac * p[node_idx[x]-node_idx[ca]] % MOD;
while( node_chain[ty] != node_chain[ca] )
{
cay += node_idx[ty] + 1;
}
cay += node_idx[ty] - node_idx[ca];
while( node_chain[y] != node_chain[ca] )
{
cay -= node_idx[y];
range_update(1, 0, chain_len[node_chain[y]]-1, 0, node_idx[y], cac*p[cay]%MOD, 0, chain[node_chain[y]]);
cay--;
}
if( node_idx[y] != node_idx[ca] )
{
range_update(1, 0, chain_len[node_chain[y]]-1, node_idx[ca]+1, node_idx[y], cac*p[1]%MOD, 0, chain[node_chain[y]]);
}
return;
}
int min(int x, int y)
{
return ( x < y ) ? x : y ;
}
int max(int x, int y>
{
return ( x > y ) ? x : y;
}
long long solve(int x, int ancestor)
{
long long ans = 0;
while( node_chain[x] != node_chain[ancestor] )
{
ans = ( ans + sum(1, 0, chain_len[node_chain[x]]-1, 0, node_idx[x], chain[node_chain[x]]) ) % MOD;
}
ans = ( ans + sum(1, 0, chain_len[node_chain[x]]-1, node_idx[ancestor], node_idx[x], chain[node_chain[x]]) ) % MOD;
return ans;
}
int main()
{
int U, Q, x, y, i;
long long R, t;
scanf("%d%lld", &N, &R);
R %= MOD;
p[0] = sp[0] = 1;
for( i = 1 ; i  < = N ; i++ )
{
p[i] = R * p[i-1] % MOD;
sp[i] = ( sp[i-1] + p[i] ) % MOD;
}
for( i = 0 ; i  <  N - 1 ; i++ )
{
scanf("%d%d", &x, &y);
insert_edge(x-1, y-1, 1);
}
preprocess();
scanf("%d%d", &U, &Q);
while(U--)
{
scanf("%d%d%lld", &x, &y, &t);
range_solve(x-1, y-1, t);
}
while(Q--)
{
scanf("%d%d", &x, &y);
i = lca(x-1, y-1);
printf("%lld\n", ( solve(x-1, i) + solve(y-1, i) - sum(1, 0, chain_len[node_chain[i]]-1, node_idx[i], node_idx[i], chain[node_chain[i]]) + MOD ) % MOD);
}
return 0;
}
``````
Copy The Code &

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
import sys

sys.setrecursionlimit(10000000)

n, r = input().strip().split(' ')
n, r = [int(n), int(r)]

g = {}
gv = {}
edge = []

for c in range(1, n):
i, j = input().strip().split(' ')
if i not in g.keys():
g[i] = []
gv[i] = 0
if j not in g.keys():
g[j] = []
gv[j] = 0

g[i].append(j)
g[j].append(i)

def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if start not in graph.keys():
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None

u, p = input().strip().split(' ')
u, p = [int(u), int(p)]

for c in range(u):
i, j, x = input().strip().split(' ')
i, j, x = [str(i), str(j), int(x)]
path = find_path(g, i, j)
for pa in path:
gv[pa] = gv[pa] + x
x *= r
for c in range(p):
i, j = input().strip().split(' ')
path = find_path(g, i, j)
s = 0
for p in path:
s += gv[p]
print(s % 100711433)

``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Solution2 {

static final int LOGN = 17;
static final int MOD = 100_711_433;

static long power(long a, int n) {
long r = 1;
for (; n > 0; n >>= 1, a = a*a%MOD) {
if ((n & 1) > 0) {
r = r*a%MOD;
}
}
return r;
}

static long add(long x, long y) {
return (x+y)%MOD;
}

static int inv(int x) {
long r = 1;
for (; x > 1; x = MOD%x) {
r = MOD/x * -r % MOD;
}
return (int) r;
}

static int[] dep;
static int[][] par;
static List < Integer>[] e;

static class Node {
int d;
int v;
int p;
Node(int d, int v, int p) {
this.d = d;
this.v = v;
this.p = p;
}
}

static void dfs(int d, int v, int p) {
Deque < Node> queue = new LinkedList<>();
while (!queue.isEmpty()) {
Node node = queue.poll();
dep[node.v] = node.d;
par[0][node.v] = node.p;
for (int u: e[node.v]) {
if (u != node.p) {
}
}
}
}

static int r;
static int invr;
static long[] d;
static long[] dd;

static class Node2 {
int v;
int p;
boolean start = true;
Node2(int v, int p) {
this.v = v;
this.p = p;
}
}

static void dfs2(int v, int p) {
Deque < Node2> queue = new LinkedList<>();
while (!queue.isEmpty()) {
Node2 node = queue.peek();
if (node.start) {
for (int u: e[node.v]) {
if (u != node.p) {
queue.push(new Node2(u, node.v));
}
}
node.start = false;
} else {
if (node.p >= 0) {
d[node.p] = add(d[node.p], d[node.v] * r);
dd[node.p] = add(dd[node.p], dd[node.v] * invr);
}
queue.remove();
}
}
}

static long[] path;

static class Node3 {
int v;
int p;
long s;
Node3(int v, int p, long s) {
this.v = v;
this.p = p;
this.s = s;
}
}

static void dfs3(int v, int p, long s) {
Deque < Node3> queue = new LinkedList<>();
while (!queue.isEmpty()) {
Node3 node = queue.poll();
path[node.v] = (node.s+d[node.v]+dd[node.v])%MOD;
for (int u: e[node.v]) {
if (u != node.p) {
queue.push(new Node3(u, node.v, (node.s+d[node.v]+dd[node.v])%MOD));
}
}
}
}

static int lca(int v, int u) {
if (dep[v]  <  dep[u]) {
int temp = v;
v = u;
u = temp;
}
for (int i = LOGN; --i >= 0; ) {
if (1 << i  < = dep[v]-dep[u]) {
v = par[i][v];
}
}
if (v == u) {
return v;
}
for (int i = LOGN; --i >= 0; ) {
if (par[i][v] != par[i][u]) {
v = par[i][v];
u = par[i][u];
}
}
return par[0][v];
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken()) % MOD;
invr = r > 0 ? inv(r) : 0;
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[LOGN][n];
dfs(0, 0, -1);
for (int j = 1; j  <  LOGN; j++) {
for (int i = 0; i  <  n; i++) {
par[j][i] = par[j-1][i] < 0 ? -1 : par[j-1][par[j-1][i]];
}
}
int upd = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
d = new long[n];
dd = new long[n];
for (int i=0; i  <  upd; i++) {
int v = Integer.parseInt(st.nextToken()) - 1;
int u = Integer.parseInt(st.nextToken()) - 1;
int w = lca(v, u);
int x = Integer.parseInt(st.nextToken());

if (r > 0) {
long xl = power(r, dep[v]-dep[w]), xr = power(r, dep[u]-dep[w]);
if (w > 0) {
d[par[0][w]] = add(d[par[0][w]], - (x * xl % MOD * r));
}
dd[u] = add(dd[u], x * xl % MOD * xr);
dd[w] = add(dd[w], - x * xl);
} else {
}
}
dfs2(0, -1);
path = new long[n];
dfs3(0, -1, 0);
for (int i=0; i  <  q; i++) {
int v = Integer.parseInt(st.nextToken()) - 1;
int u = Integer.parseInt(st.nextToken()) - 1;
int w = lca(v, u);
long result = ((path[v]+path[u]-path[w]-(w > 0 ? path[par[0][w]] : 0)) % MOD + MOD) % MOD;
bw.write(String.valueOf(result) + "\n");
}

bw.newLine();
bw.close();
br.close();
}
}
``````
Copy The Code &