Algorithm

Problem Name: Data Structures - Easy Addition

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

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 & Try With Live Editor

#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 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;
        addB = f;
    }
    
    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);
        f = (x.addB + addB);
        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::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::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;
        fwd[root].addB = (fwd[root].addB + 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;
        bck[root].addB = (bck[root].addB + bck[*it].addB * Rinv) % 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::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.addB = brt + brt;
    if(B.addB >= mod) B.addB -= 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.addB = brt + brt;
    if(A.addB >= mod) A.addB -= 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 & Try With Live Editor

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

  static int highestOneBitMask(int v) {
    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 vertices = new LinkedList<>();
      indices = new int[n];

      int currentIndex = 1;
      vertices.add(0);
      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;
          vertices.add(u);
        }
      }

      int head = 0;
      int tail = 1;
      int[] vertices2 = new int[n];
      while(head != tail) {
        int v = vertices2[head++];
        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 hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);
      int j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);

      int x, y;
      if(j == hIv) {
        x = v;
      } else {
        int kMask = highestOneBitMask(ancestorHeights[v] & (j-1));
        x = pathParents[(indices[v] & ~kMask | (kMask+1))-1];
      }
      if(j == hIu) {
        y = u;
      } else {
        int kMask = highestOneBitMask(ancestorHeights[u] & (j-1));
        y = pathParents[(indices[u] & ~kMask | (kMask+1))-1];
      }
      return indices[x] < indices[y] ? x : y;
    }
  }

  
  static int[] tParent;
  static List 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 stk = new LinkedList<>();
    stk.add(root);
    while(!stk.isEmpty()) {
      int i = stk.remove();
      tOrd.add(i);
      for(int j = g[i].size()-1; j >= 0; j--) {
        int c = g[i].get(j);
        if(tParent[c] == -1 && c != root) {
          stk.add(c);
        } 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;
    }
    adds[a] = (int)sum(adds[a], x);
    adds[b] = (int)sum(adds[b], MOD-x);
  }
    
  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 {

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

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

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

      g[x].add(y);
      g[y].add(x);
    }
    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++) {
      addEdge(tParent[i], i);
    }
    
    SchieberVishkinLCA lca = new SchieberVishkinLCA();
    lca.build(n);

    int[] powRs = getPowRs(n, r);
    int[][] adds = new int[T][n+1];

    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    for (int i = 0; i < u; i++) {
      st = new StringTokenizer(br.readLine());
      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);
      querysub(adds[0], a, cp, mult(t, p0));
      querysub(adds[1], b, c,  mult(t, q0));

      t = (int) sum(mult(a1, d2), mult(d1, a2));
      int e = -dB+uB;
      querysub(adds[2], a, cp, mult(t, p0));
      querysub(adds[0], a, cp, mult(t, p0, dA));
      querysub(adds[3], b, c,  mult(t, q0));
      querysub(adds[1], b, c,  mult(t, q0, e));
      
      t = (int) mult(d1, d2);
      querysub(adds[4], a, cp, mult(t, p0));
      querysub(adds[2], a, cp, mult(t, p0, dA, 2));
      querysub(adds[0], a, cp, mult(t, p0, dA, dA));
      querysub(adds[5], b, c,  mult(t, q0));
      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);
        adds[t][tParent[i]] = (int) sum(adds[t][tParent[i]], adds[t][i]);
      }
      for (int i = 0; i < n; i++) {
        adds[t][i] = (int) mult(adds[t][i], coefs[t][i]);
      }
      for (int i = 0; i < n; i++) {
        values[i] = (int) sum(values[i], adds[t][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++) {
      st = new StringTokenizer(br.readLine());
      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 & Try With Live Editor

Demonstration

Previous
[Solved] Network administration solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Find the permutation solution in Hackerrank - Hacerrank solution C, C++, java,js, Python