## Algorithm

Problem Name: Data Structures - Easy Addition

In this HackerRank in Data Structures - Easy Addition 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.

Initially all node values are zero.

The update query is of the format

a1 d1 a2 d2 A B


This means you'd have to add (a1 + z * d1) * (a2 + z * d2) * Rz in all nodes in the path from A to B where

is the distance between the node and A.

The retrieval query is of the format

i j


You need to return the sum of the node values lying in the path from node i to node j modulo 1000000007.

Note:

1. First all update queries are given and then all retrieval queries.
2. Distance between 2 nodes is the shortest path length between them taking each edge weight as 1.

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 x y separated by a single space denotes an edge between nodes x and y.

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 6 space separated integers (a1,d1,a2,d2,A and B 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 <= 105
2 <= R <= 109
1 <= U <= 105
1 <= Q <= 105
1 <= a1,a2,d1,d2 <= 108
1 <= x, y, i, j, A, B <= N

Note
For the update operation, x can be equal to y and for the query operation, i can be equal to j.

Sample Input

7 2
1 2
1 3
2 4
2 6
4 5
6 7
1 4
1 1 1 1 4 6
4 5
2 7
4 7
5 3


Sample Output

1
44
45
9


Explanation

The node values after updation becomes :

0 8 0 1 0 36 0


Answer to Query #1: 1+0 = 1

Answer to Query #2: 8+36+0 = 44

Answer to Query #3: 1+8+36+0 = 45

Answer to Query #4: 0+1+8+0+0 = 9

## Code Examples

### #1 Code Example with C Programming

Code - C Programming


#include<stdio.h>
#include<stdlib.h>
#define MOD 1000000007
typedef struct _lnode
{
int x;
int w;
struct _lnode *next;
}lnode;
typedef struct _data
{
long long term10_fa;
long long term20_fa;
long long term21_fa;
long long term30_fa;
long long term31_fa;
long long term32_fa;
long long term10_ia;
long long term20_ia;
long long term21_ia;
long long term30_ia;
long long term31_ia;
long long term32_ia;
long long term10_fs;
long long term20_fs;
long long term21_fs;
long long term30_fs;
long long term31_fs;
long long term32_fs;
long long term10_is;
long long term20_is;
long long term21_is;
long long term30_is;
long long term31_is;
long long term32_is;
}data;
int N, R, RI, DP[18][100000], level[100000];
long long s[100000], dis[100000], Rp[100005], IRp[100005];
lnode *table[100000] = {0};
data tree[100000] = {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 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]];
}
}
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];
}
void dfs0(int u)
{
lnode *x;
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);
}
}
return;
}
void dfs1(int u)
{
lnode *x;
for( x = table[u] ; x ; x = x -> next )
{
if( x -> x != DP[0][u] )
{
dfs1(x -> x);
tree[u].term10_fa = ( tree[u].term10_fa + tree[x -> x].term10_fa * R ) % MOD;
tree[u].term10_ia = ( tree[u].term10_ia + tree[x -> x].term10_ia * RI ) % MOD;
tree[u].term10_fs = ( tree[u].term10_fs + tree[x -> x].term10_fs * R ) % MOD;
tree[u].term10_is = ( tree[u].term10_is + tree[x -> x].term10_is * RI ) % MOD;
tree[u].term20_fa = ( tree[u].term20_fa + tree[x -> x].term20_fa * R ) % MOD;
tree[u].term21_fa = ( tree[u].term21_fa + ( tree[x -> x].term21_fa + tree[x -> x].term20_fa ) * R ) % MOD;
tree[u].term20_ia = ( tree[u].term20_ia + tree[x -> x].term20_ia * RI ) % MOD;
tree[u].term21_ia = ( tree[u].term21_ia + ( tree[x -> x].term21_ia - tree[x -> x].term20_ia + MOD ) * RI ) % MOD;
tree[u].term20_fs = ( tree[u].term20_fs + tree[x -> x].term20_fs * R ) % MOD;
tree[u].term21_fs = ( tree[u].term21_fs + ( tree[x -> x].term21_fs + tree[x -> x].term20_fs ) * R ) % MOD;
tree[u].term20_is = ( tree[u].term20_is + tree[x -> x].term20_is * RI ) % MOD;
tree[u].term21_is = ( tree[u].term21_is + ( tree[x -> x].term21_is - tree[x -> x].term20_is + MOD ) * RI ) % MOD;
tree[u].term30_fa = ( tree[u].term30_fa + tree[x -> x].term30_fa * R ) % MOD;
tree[u].term31_fa = ( tree[u].term31_fa + ( tree[x -> x].term31_fa + tree[x -> x].term30_fa ) * R ) % MOD;
tree[u].term32_fa = ( tree[u].term32_fa + ( tree[x -> x].term32_fa + 2 * tree[x -> x].term31_fa + tree[x -> x].term30_fa ) * R ) % MOD;
tree[u].term30_ia = ( tree[u].term30_ia + tree[x -> x].term30_ia * RI ) % MOD;
tree[u].term31_ia = ( tree[u].term31_ia + ( tree[x -> x].term31_ia - tree[x -> x].term30_ia + MOD ) * RI ) % MOD;
tree[u].term32_ia = ( tree[u].term32_ia + ( tree[x -> x].term32_ia - 2 * tree[x -> x].term31_ia + tree[x -> x].term30_ia + 2 * MOD ) * RI ) % MOD;
tree[u].term30_fs = ( tree[u].term30_fs + tree[x -> x].term30_fs * R ) % MOD;
tree[u].term31_fs = ( tree[u].term31_fs + ( tree[x -> x].term31_fs + tree[x -> x].term30_fs ) * R ) % MOD;
tree[u].term32_fs = ( tree[u].term32_fs + ( tree[x -> x].term32_fs + 2 * tree[x -> x].term31_fs + tree[x -> x].term30_fs ) * R ) % MOD;
tree[u].term30_is = ( tree[u].term30_is + tree[x -> x].term30_is * RI ) % MOD;
tree[u].term31_is = ( tree[u].term31_is + ( tree[x -> x].term31_is - tree[x -> x].term30_is + MOD ) * RI ) % MOD;
tree[u].term32_is = ( tree[u].term32_is + ( tree[x -> x].term32_is - 2 * tree[x -> x].term31_is + tree[x -> x].term30_is + 2 * MOD ) * RI ) % MOD;
}
}
s[u] = ( tree[u].term10_fa + tree[u].term10_ia - tree[u].term10_fs - tree[u].term10_is + 2 * MOD ) % MOD;
s[u] = ( s[u] + tree[u].term21_fa + tree[u].term21_ia - tree[u].term21_fs - tree[u].term21_is + 2 * MOD ) % MOD;
s[u] = ( s[u] + tree[u].term32_fa + tree[u].term32_ia - tree[u].term32_fs - tree[u].term32_is + 2 * MOD ) % MOD;
return;
}
void dfs2(int u)
{
lnode *x;
if( u != DP[0][u] )
{
dis[u] = ( s[u] + dis[DP[0][u]] ) % MOD;
}
else
{
dis[u] = s[u];
}
for( x = table[u] ; x ; x = x -> next )
{
if( x -> x != DP[0][u] )
{
dfs2(x -> x);
}
}
return;
}
long long modInverse(long long a, long long mod)
{
long long b0 = mod, t, q;
long long x0 = 0, x1 = 1;
while( a > 1 )
{
q = a / mod;
t = mod;
mod = a % mod;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if( x1 < 0 )
{
x1 += b0;
}
return x1;
}
int main()
{
int U, Q, x, y, a1, a2, d1, d2, t1, t2, i;
long long ans;
scanf("%d%d", &N, &R);
for( i = 0 ; i  <  N - 1 ; i++ )
{
scanf("%d%d", &x, &y);
insert_edge(x-1, y-1, 1);
}
preprocess();
RI = modInverse(R, MOD);
Rp[0] = IRp[0] = 1;
for( i = 1 ; i  <  100005 ; i++ )
{
Rp[i] = Rp[i-1] * R % MOD;
IRp[i] = IRp[i-1] * RI % MOD;
}
scanf("%d%d", &U, &Q);
while(U--)
{
scanf("%d%d%d%d%d%d", &a1, &d1, &a2, &d2, &x, &y);
i = lca(x-1, y-1);
t1 = level[x-1] - level[i];
t2 = level[y-1] - level[i];
tree[x-1].term10_fa = ( tree[x-1].term10_fa + a1 * (long long)a2 ) % MOD;
tree[x-1].term20_fa = ( tree[x-1].term20_fa + a1 * (long long)d2 + a2 * (long long)d1 ) % MOD;
tree[x-1].term30_fa = ( tree[x-1].term30_fa + d1 * (long long)d2 ) % MOD;
tree[i].term10_fs = ( tree[i].term10_fs + a1 * (long long)a2 % MOD * Rp[t1] ) % MOD;
tree[i].term20_fs = ( tree[i].term20_fs + ( a1 * (long long)d2 + a2 * (long long)d1 ) % MOD * Rp[t1] ) % MOD;
tree[i].term21_fs = ( tree[i].term21_fs + ( a1 * (long long)d2 + a2 * (long long)d1 ) % MOD * t1 % MOD * Rp[t1] ) % MOD;
tree[i].term30_fs = ( tree[i].term30_fs + d1 * (long long)d2 % MOD * Rp[t1] ) % MOD;
tree[i].term31_fs = ( tree[i].term31_fs + d1 * (long long)d2 % MOD * t1 % MOD * Rp[t1] ) % MOD;
tree[i].term32_fs = ( tree[i].term32_fs + d1 * (long long)d2 % MOD * t1 % MOD * t1 % MOD * Rp[t1] ) % MOD;
tree[y-1].term10_ia = ( tree[y-1].term10_ia + a1 * (long long)a2 % MOD * Rp[t1+t2] ) % MOD;
tree[y-1].term20_ia = ( tree[y-1].term20_ia + ( a1 * (long long)d2 + a2 * (long long)d1 ) % MOD * Rp[t1+t2] ) % MOD;
tree[y-1].term21_ia = ( tree[y-1].term21_ia + ( a1 * (long long)d2 + a2 * (long long)d1 ) % MOD * ( t1 + t2 ) % MOD * Rp[t1+t2] ) % MOD;
tree[y-1].term30_ia = ( tree[y-1].term30_ia + d1 * (long long)d2 % MOD * Rp[t1+t2] ) % MOD;
tree[y-1].term31_ia = ( tree[y-1].term31_ia + d1 * (long long)d2 % MOD * ( t1 + t2 ) % MOD * Rp[t1+t2] ) % MOD;
tree[y-1].term32_ia = ( tree[y-1].term32_ia + d1 * (long long)d2 % MOD * ( t1 + t2 ) % MOD * ( t1 + t2 ) % MOD * Rp[t1+t2] ) % MOD;
if(i)
{
tree[DP[0][i]].term10_is = ( tree[DP[0][i]].term10_is + a1 * (long long)a2 % MOD * Rp[t1+t2] % MOD * IRp[t2+1] ) % MOD;
tree[DP[0][i]].term20_is = ( tree[DP[0][i]].term20_is + ( a1 * (long long)d2 + a2 * (long long)d1 ) % MOD * Rp[t1+t2] % MOD * IRp[t2+1] ) % MOD;
tree[DP[0][i]].term21_is = ( tree[DP[0][i]].term21_is + ( a1 * (long long)d2 + a2 * (long long)d1 ) % MOD * ( t1 - 1 + MOD ) % MOD * Rp[t1+t2] % MOD * IRp[t2+1] ) % MOD;
tree[DP[0][i]].term30_is = ( tree[DP[0][i]].term30_is + d1 * (long long)d2 % MOD * Rp[t1+t2] % MOD * IRp[t2+1] ) % MOD;
tree[DP[0][i]].term31_is = ( tree[DP[0][i]].term31_is + d1 * (long long)d2 % MOD * ( t1 - 1 + MOD ) % MOD * Rp[t1+t2] % MOD * IRp[t2+1] ) % MOD;
tree[DP[0][i]].term32_is = ( tree[DP[0][i]].term32_is + d1 * (long long)d2 % MOD * ( t1 - 1 + MOD ) % MOD * ( t1 - 1 + MOD ) % MOD * Rp[t1+t2] % MOD * IRp[t2+1] ) % MOD;
}
}
dfs1(0);
dfs2(0);
while(Q--)
{
scanf("%d%d", &x, &y);
a1 = lca(x-1, y-1);
ans = ( dis[x-1] + dis[y-1] - dis[a1] + MOD ) % MOD;
if(a1)
{
ans = ( ans - dis[DP[0][a1]] + MOD ) % MOD;
}
printf("%lld\n", ans>;
}
return 0;
}

Copy The Code &

### #2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i  < = (b); i++)
typedef long long int ll;

const int mod = 1000000007;
vector<int> myvector[100001];
int N, parent[100001], depth[100001], Q, U;
ll R, Rinv, Rp[100001], sum[100001];
int store[100001], Root[100001][18];

struct node{
ll S, D, B, factD, factB, addB;
node(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0, ll f = 0){
S = a, D = b, B = c;
factD = d;
factB = e;
}

node operator + (const node &x) const{
ll a, b, c, d, e, f;
a = (x.S + S);
b = (x.D + D);
c = (x.B + B);
d = (x.factD + factD);
e = (x.factB + factB);
a = (a > mod) ? (a - mod) : a;
b = (b > mod) ? (b - mod) : b;
c = (c > mod) ? (c - mod) : c;
d = (d > mod) ? (d - mod) : d;
e = (e > mod) ? (e - mod) : e;
f = (f > mod) ? (f - mod) : f;
return node(a, b, c, d, e, f);
}

} fwd[100001], bck[100001], A, B;

ll inverse(ll a, ll b){
ll Remainder, p0 = 0, p1 = 1, pcurr = 1, q, m = b;
while(a != 0){
Remainder = b % a;
q = b / a;
if(Remainder != 0){
pcurr = p0 - (p1 * q) % m;
if(pcurr < 0)
pcurr += m;
p0 = p1;
p1 = pcurr;
}
b = a;
a = Remainder;
}
return pcurr;
}

void dfs_pre(int root){
for(vector<int>::iterator it = myvector[root].begin(); it != myvector[root].end(); it++){
if(parent[root] == *it) continue;
parent[*it] = root;
depth[*it] = depth[root] + 1;
dfs_pre(*it);
}
}

void dfs_cal(int root){
for(vector<int>::iterator it = myvector[root].begin(); it != myvector[root].end(); it++){
if(parent[root]==*it) continue;
dfs_cal(*it);
fwd[root].S = (fwd[root].S + fwd[*it].S * R) % mod;
fwd[root].D = (fwd[root].D + (fwd[*it].D + fwd[*it].factD) * R) % mod;
fwd[root].factD = (fwd[root].factD + fwd[*it].factD * R) % mod;
fwd[root].B = (fwd[root].B +  (fwd[*it].B + fwd[*it].factB) * R) % mod;
fwd[root].factB = (fwd[root].factB + (fwd[*it].factB + fwd[*it].addB) * R) % mod;
bck[root].S = (bck[*it].S * Rinv + bck[root].S) % mod;
bck[root].D = (bck[root].D + (bck[*it].D - bck[*it].factD) * Rinv) % mod;
if(bck[root].D  <  0) bck[root].D += mod;
bck[root].factD = (bck[root].factD + bck[*it].factD * Rinv) % mod;
bck[root].B = (bck[root].B + (bck[*it].B - bck[*it].factB) * Rinv) % mod;
if(bck[root].B < 0) bck[root].B += mod;
bck[root].factB = (bck[root].factB + (bck[*it].factB - bck[*it].addB) * Rinv) % mod;
if(bck[root].factB < 0) bck[root].factB += mod;
}
sum[root] = (sum[root] + fwd[root].S + fwd[root].D + fwd[root].B + bck[root].S + bck[root].D + bck[root].B) % mod;
}

void dfs_sum(int root)      {
for(vector<int>::iterator it = myvector[root].begin(); it != myvector[root].end(); it++){
if(parent[root] == *it) continue;
sum[*it] = (sum[*it] + sum[root]) % mod;
dfs_sum(*it);
}
}

void init(){
store[0] = 0; store[1] = 0; store[2] = 1;
int cmp = 4;
FOR(i, 3, 100000>{
if(cmp > i) store[i] = store[i - 1];
else{
store[i] = store[i - 1] + 1;
cmp <<= 1;
}
}
}

void process(int N){
memset(Root, -1, sizeof(Root));
for(int i = 1; i <= N; i++) Root[i][0]=parent[i];
for(int i = 1; (1 << i)  < = N; i++)
for(int j = 1; j  < = N; j++)
if(Root[j][i - 1] != -1)
Root[j][i] = Root[Root[j][i - 1]][i - 1];
}

int lca(int p, int q>{
int temp;
if(depth[p] > depth[q]) swap(p, q);
int steps = store[depth[q]];
for(int i = steps; i >= 0; i--)
if(depth[q] - (1 << i) >= depth[p])
q = Root[q][i];
if(p == q) return p;
for(int i = steps; i >= 0; i--){
if(Root[p][i] != Root[q][i])
p = Root[p][i], q = Root[q][i];
}
return parent[p];
}

void Update_forward(ll S, ll D, ll B1, ll t, int x, int y){
ll brt;
A.S = S;
B.S = mod - (S * Rp[t]) % mod;
A.factD = D;
A.D = 0;
B.factD = mod - (D * Rp[t]) % mod;
if(B.factD < 0) B.factD += mod;
B.D = (B.factD * t) % mod;
brt = B1;
A.B = 0;
A.factB = brt;
if(A.factB  <  0) A.factB += mod;
A.addB = (brt + brt) % mod;
brt = mod - (B1 * Rp[t]) % mod;
if(brt  <  0) brt += mod;
B.B = ((ll)((t * t) % mod) * brt) % mod;
B.factB = ((ll)(2 * t + 1) * brt) % mod;
B.addB = (brt + brt) % mod;
fwd[x] = fwd[x] + A;
if(y != 1) fwd[parent[y]] = fwd[parent[y]] + B;
}

void Update_backward(ll S,ll D,ll B1,ll t,ll g,int y,int x){
ll brt;
B.S = (S * Rp[t]) % mod;
A.S = mod - (S * Rp[g]) % mod;
B.factD = (D * Rp[t]) % mod;
B.D = (t * B.factD) % mod;
A.factD = mod - (D * Rp[g]) % mod;
A.D = (g * A.factD) % mod;
brt = (B1 * Rp[t]> % mod;
B.factB = ((ll)(2 * t - 1) * brt) % mod;
if(B.factB < 0) B.factB += mod;
B.B = ((ll)((t * t) % mod) * brt) % mod;
brt = mod - (B1 * Rp[g]) % mod;
if(brt  <  0> brt += mod;
A.factB = ((ll)(2 * g - 1) * brt) % mod;
if(A.factB < 0) A.factB += mod;
A.B = ((ll)((g * g) % mod) * brt) % mod;
bck[y] = bck[y] + B;
bck[x] = bck[x] + A;
}

void solve(){
ll S1, D1, B1, ans;
int Z, anc, x, y, a1, a2, d1, d2;
scanf("%d%lld", &N, &R);
Rinv = inverse(R, mod);
FOR(i, 1, N - 1){
scanf("%d%d", &x, &y);
myvector[x].push_back(y);
myvector[y].push_back(x);
}
parent[1] = 1;
depth[1] = 0;
dfs_pre(1);
process(N);
Rp[0] = 1;
FOR(i, 1, N) Rp[i] = ((ll)Rp[i - 1] * (ll)R) % mod;
scanf("%d%d", &U, &Q);
while(U--){
scanf("%d%d%d%d%d%d", &a1, &d1, &a2, &d2, &x, &y);
S1 = ((ll)a1 * (ll)a2) % mod;
D1 = ((ll)d1 * (ll)a2 + (ll)d2 * (ll)a1) % mod;
B1 = ((ll)d1 * (ll)d2) % mod;
anc = lca(x, y);
Update_forward(S1, D1, B1, depth[x] - depth[anc] + 1, x, anc);
Update_backward(S1, D1, B1, depth[y] + depth[x] - 2 * depth[anc], depth[x] - depth[anc], y, anc);
}
dfs_cal(1);
dfs_sum(1);
while(Q--){
scanf("%d%d", &x, &y);
anc = lca(x, y);
if(anc != 1) ans = (sum[x] + sum[y] - sum[anc] - sum[parent[anc]]) % mod;
else ans = (sum[x] + sum[y] - sum[anc]) % mod;
if(ans  <  0) printf("%lld\n", ans + mod);
else printf("%lld\n", ans);
}
}

int main(){
init();
solve(>;
return 0;
}


Copy The Code &

### #3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;

public class Solution {

static int[] nxt;
static int[] succ;
static int[] ptr;
static int index = 1;

static void addEdge(int u, int v) {
nxt[index] = ptr[u];
ptr[u] = index;
succ[index++] = v;
}

static int lowestOneBit(int v) {
return v & (~v+1);
}

v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return v >> 1;
}

static class SchieberVishkinLCA {
int[] indices;
int[] maxHIndices;
int[] ancestorHeights;
int[] pathParents;

void build(int n) {
ancestorHeights = new int[n];
int[] parents = new int[n];
maxHIndices = new int[n];
Deque < Integer> vertices = new LinkedList<>();
indices = new int[n];

int currentIndex = 1;
while(!vertices.isEmpty()) {
int v = vertices.removeLast();
indices[v] = currentIndex++;
for(int it = ptr[v]; it > 0; it = nxt[it]) {
int u = succ[it];
parents[u] = v;
}
}

int tail = 1;
int[] vertices2 = new int[n];
for(int it = ptr[v]; it > 0; it = nxt[it]) {
int u = succ[it];
vertices2[tail++] = u;
}
}

for (int i = 0; i  <  tail; i++) {
int it = vertices2[i];
maxHIndices[it] = indices[it];
}
for (int i = tail-1; i >= 0; i--) {
int it = vertices2[i];
int v = it;
int parent = parents[v];
if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v])) {
maxHIndices[parent] = maxHIndices[v];
}
}

ancestorHeights[0] = 0;
for (int i = 0; i  <  tail; i++) {
int it = vertices2[i];
int v = it;
ancestorHeights[v] = ancestorHeights[parents[v]] | lowestOneBit(maxHIndices[v]);
}

int[] temp = parents;
parents = pathParents;
pathParents = temp;

pathParents[indices[0]-1] = 0;
for (int i = 0; i  <  tail; i++> {
int it = vertices2[i];
int v = it;
for(int jt = ptr[v]; jt > 0; jt = nxt[jt]) {
int u = succ[jt];
if(maxHIndices[v] != maxHIndices[u]) {
pathParents[indices[u]-1] = v;
} else {
pathParents[indices[u]-1] = pathParents[indices[v]-1];
}
}
}
}

int query(int v, int u) {
int Iv = maxHIndices[v];
int Iu = maxHIndices[u];
int hIv = lowestOneBit(Iv);
int hIu = lowestOneBit(Iu);
int j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);

int x, y;
if(j == hIv) {
x = v;
} else {
}
if(j == hIu) {
y = u;
} else {
}
return indices[x]  <  indices[y] ? x : y;
}
}

static int[] tParent;
static List < Integer> tOrd = new ArrayList<>();

static void treeGetorder(List[] g, int root) {
int n = g.length;
tParent = new int[n];
Arrays.fill(tParent, -1);
tOrd.clear();

Deque < Integer> stk = new LinkedList<>();
while(!stk.isEmpty()) {
int i = stk.remove();
for(int j = g[i].size()-1; j >= 0; j--) {
int c = g[i].get(j);
if(tParent[c] == -1 && c != root) {
} else {
tParent[i] = c;
}
}
}
}

static final long MOD = 1000000007;

static long sum(long a, long b) {
return (a + b) % MOD;
}

static long mult(long a, long b) {
return (a * b) % MOD;
}

static long mult(long a, long b, long c) {
return (a * ((b*c) % MOD)) % MOD;
}

static long mult(long a, long b, long c, long d) {
return mult(mult(a, b), mult(c, d));
}

static void querysub(int[] adds, int a, int b, long x) {
if (x < 0) {
x += MOD;
}
}

static long inverse(int x> {
long a = x;
long b = MOD;
long u = 1;
long v = 0;
while(b > 0) {
long t = a / b;
a -= t * b;

long temp = a;
a = b;
b = temp;

u = sum(u, MOD - mult(t, v));

temp = u;
u = v;
v = temp;
}
return u;
}

static int[] getPowRs(int n, int r) {
int[] powRs = new int[n*2+1];
powRs[n] = 1;
for(int i = 1; i  < = n; i++) {
powRs[n+i] = (int) mult(powRs[n+i-1], r);
}
long invR = inverse(r);
for(int i = 1; i  < = n; i++) {
powRs[n-i] = (int) mult(powRs[n-i+1], invR);
}
return powRs;
}

static int[][] getCoefs(int n, int r, int[] powRs, int[] depth) {
int[][] coefs = new int[T][n+1];
for(int i = 0; i  <  n; i++) {
int d = depth[i];
coefs[0][i] = powRs[n-d];
coefs[1][i] = powRs[n+d];
coefs[2][i] = (int) mult(powRs[n-d], MOD-d);
coefs[3][i] = (int) mult(powRs[n+d], +d);
coefs[4][i] = (int) mult(powRs[n-d], MOD-d, MOD-d);
coefs[5][i] = (int) mult(powRs[n+d], +d, +d);
}
return coefs;
}

static final int T = 6;

static void print(int[] arr, int n, String s) {
System.out.print(s + ": ");
for (int i = 0; i  <  n; i++) {
System.out.print(arr[i] + " ");
}
System.out.print("\n");
}

@SuppressWarnings("unchecked")
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 r = Integer.parseInt(st.nextToken());

List < Integer>[] g = new List[n];
for (int i = 0; i  <  n; i++) {
g[i] = new ArrayList<>();
}

for (int i = 0; i  <  n - 1; i++) {
int x = Integer.parseInt(st.nextToken())-1;
int y = Integer.parseInt(st.nextToken())-1;

}
treeGetorder(g, 0);
int[] depth = new int[n];
for (int j = 1; j  <  n; j++) {
int i = tOrd.get(j);
depth[i] = depth[tParent[i]] + 1;
}

nxt = new int[n];
succ = new int[n];
ptr = new int[n];
for (int i = 1; i  <  n; i++) {
}

SchieberVishkinLCA lca = new SchieberVishkinLCA();
lca.build(n);

int[] powRs = getPowRs(n, r);

int u = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());

for (int i = 0; i  <  u; i++) {
int a1 = Integer.parseInt(st.nextToken());
int d1 = Integer.parseInt(st.nextToken());
int a2 = Integer.parseInt(st.nextToken());
int d2 = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;

int c = lca.query(a, b);
int cp = c == 0 ? n : tParent[c];

int dA = depth[a], dB = depth[b], dC = depth[c];
int p0 = powRs[n+dA];
int uB = dA + dB - dC * 2;
int q0 = powRs[n-dB+uB];
int t = (int) mult(a1, a2);

t = (int) sum(mult(a1, d2), mult(d1, a2));
int e = -dB+uB;
querysub(adds[0], a, cp, mult(t, p0, dA));
querysub(adds[1], b, c,  mult(t, q0, e));

t = (int) mult(d1, d2);
querysub(adds[2], a, cp, mult(t, p0, dA, 2));
querysub(adds[0], a, cp, mult(t, p0, dA, dA));
querysub(adds[3], b, c,  mult(t, q0, e, 2));
querysub(adds[1], b, c,  mult(t, q0, e, e));
}
int coefs[][] = getCoefs(n, r, powRs, depth);
int[] values = new int[n];
for(int t = 0; t  <  T; t++) {
for(int ix = n-1; ix > 0; -- ix) {
int i = tOrd.get(ix);
}
for (int i = 0; i  <  n; i++) {
}
for (int i = 0; i  <  n; i++) {
}
}
int[] sums = values.clone();
for(int ix = 1; ix  <  n; ix++) {
int i = tOrd.get(ix);
sums[i] = (int) sum(sums[i], sums[tParent[i]]);
}

for (int ii = 0; ii  <  q; ii++) {
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;

int c = lca.query(a, b);
long result = 0;
result = sum(result, sums[a]);
result = sum(result, sums[b]);
result = sum(result, MOD-values[c]);
if(c != 0) {
result = sum(result, MOD - mult(sums[tParent[c]], 2));
}
bw.write(result + "\n");
}

bw.newLine();
bw.close();
br.close();
}
}

Copy The Code &