In this HackerRank Easy Addition problem solution, you are given a tree with N nodes and each node 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.

we need to return the sum of the node values lying under the path from i to j and then modulo with 1000000007 value.

hackerrank easy addition problem solution


Problem solution in 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<Integer> 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<Integer> tOrd = new ArrayList<>();

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

    Deque<Integer> 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<Integer>[] 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();
  }
}


Problem solution in C++ programming.

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

template<int MOD>
struct ModInt {
    static const int Mod = MOD;
    unsigned x;
    ModInt(): x(0) { }
    ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
    ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
    int get() const { return (int)x; }
    
    ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    
    ModInt inverse() const {
        long long a = x, b = MOD, u = 1, v = 0;
        while(b) {
            long long t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        return ModInt(u);
    }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
typedef ModInt<1000000007> mint;

struct To {
    typedef int Vertex;
    Vertex to;
    To() { }
    To(Vertex to_): to(to_) { }
};
template<typename To_>
struct StaticGraph {
    typedef To_ To;
    typedef typename To::Vertex Vertex;
    typedef std::pair<Vertex,To> Edge;
    typedef const To *const_iterator;
 
    void init(int n_, const std::vector<Edge> &edges) {
        n = n_; int m = edges.size();
        tos.resize(m+1); offsets.resize(n+1);
        for(int e = 0; e < m; e ++) offsets[edges[e].first] ++;
        for(int v = 1; v <= n_; v ++) offsets[v] += offsets[v-1];
        for(int e = 0; e < m; e ++)
            tos[-- offsets[edges[e].first]] = edges[e].second;
    }
    int numVertices() const { return n; }
    int numEdges() const { return tos.size() - 1; }
 
    inline const_iterator edgesBegin(int v) const { return &tos[offsets[v]]; }
    inline const_iterator edgesEnd(int v) const { return &tos[offsets[v+1]]; }
private:
    int n;
    std::vector<To> tos;
    std::vector<int> offsets;
};

class SchieberVishkinLCA {
public:
    typedef StaticGraph<To> Graph;
    typedef unsigned Word;
    typedef Graph::Vertex Vertex;
private:

    static inline Word lowestOneBit(Word v) {
        return v & (~v+1);
    }
    static inline Word highestOneBitMask(Word v) {
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        return v >> 1;
    }

    std::vector<Word> indices;            //Vertex -> index
    std::vector<Word> maxHIndices;        //Vertex -> index
    std::vector<Word> ancestorHeights;    //Vertex -> Word
    std::vector<Vertex> pathParents;    //index-1 -> Vertex
public:
    //g
    void build(const Graph &g, Vertex root) {
        return build(g, std::vector<Vertex>(1, root));
    }
    void build(const Graph &g, const std::vector<Vertex> &roots) {
        int N = g.numVertices();

        ancestorHeights.resize(N);
        std::vector<Vertex> parents(N);
        maxHIndices.resize(N);
        std::vector<Vertex> vertices; vertices.reserve(N);
        indices.resize(N);

        //inorder traversal
        Word currentIndex = 1;
        for(int ri = 0; ri < (int)roots.size(); ri ++) {
            Vertex root = roots[ri];
            parents[root] = root;    //
            vertices.push_back(root);
        }
        while(!vertices.empty()) {
            Vertex v = vertices.back(); vertices.pop_back();
            indices[v] = currentIndex ++;
            for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it) {
                parents[it->to] = v;
                vertices.push_back(it->to);
            }
        }

        //BFS ()
        int head = 0, tail = roots.size();
        vertices.resize(N);
        for(int ri = 0; ri < (int)roots.size(); ri ++)
            vertices[ri] = roots[ri];
        while(head != tail) {
            Vertex v = vertices[head ++];
            for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it)
                vertices[tail ++] = it->to;
        }

        //
        for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it)
            maxHIndices[*it] = indices[*it];
        for(std::vector<Vertex>::const_reverse_iterator it = vertices.rbegin(); it != vertices.rend(); ++ it) {
            Vertex v = *it, parent = parents[v];
            if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v]))
                maxHIndices[parent] = maxHIndices[v];
        }

        //A
        for(int ri = 0; ri < (int)roots.size(); ri ++) {
            Vertex root = roots[ri];
            ancestorHeights[root] = 0;
        }
        for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
            Vertex v = *it;
            ancestorHeights[v] = ancestorHeights[parents[v]] | lowestOneBit(maxHIndices[v]);
        }

        pathParents.swap(parents);    //
        for(int ri = 0; ri < (int)roots.size(); ri ++) {
            Vertex root = roots[ri];
            pathParents[indices[root]-1] = root;
        }
        for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
            Vertex v = *it;
            for(const Graph::To *jt = g.edgesBegin(v); jt != g.edgesEnd(v); ++ jt) {
                if(maxHIndices[v] != maxHIndices[jt->to])
                    pathParents[indices[jt->to]-1] = v;
                else
                    pathParents[indices[jt->to]-1] = pathParents[indices[v]-1];
            }
        }
    }

    Vertex query(Vertex v, Vertex u) const {
        //binary treeLCA
        Word Iv = maxHIndices[v], Iu = maxHIndices[u];
        Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu);
        Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);
        Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);
        //j = hI(lca(v,u))  (hI(x) = 2^(complete binary treeI(x)), I(x) = maxHIndices[x])
        //(hI(lca(v,u)) = j)hI(v)hI(u)
        Vertex x, y;
        if(j == hIv) x = v;
        else {            //lcav
            Word kMask = highestOneBitMask(ancestorHeights[v] & (j-1));    //vj
            x = pathParents[(indices[v] & ~kMask | (kMask+1))-1];    //indices[v]k
        }
        if(j == hIu) y = u;
        else {            //lcau
            Word kMask = highestOneBitMask(ancestorHeights[u] & (j-1));    //uj
            y = pathParents[(indices[u] & ~kMask | (kMask+1))-1];    //indices[u]k
        }
        return indices[x] < indices[y] ? x : y;    //in-order
    }
};
vector<int> t_parent;
vi t_ord;

void tree_getorder(const vector<vi> &g, int root) {
    int n = g.size();
    t_parent.assign(n, -1);
    t_ord.clear();

    vector<int> stk; stk.push_back(root);
    while(!stk.empty()) {
        int i = stk.back(); stk.pop_back();
        t_ord.push_back(i);
        for(int j = (int)g[i].size()-1; j >= 0; j --) {
            int c = g[i][j];
            if(t_parent[c] == -1 && c != root)
                stk.push_back(c);
            else
                t_parent[i] = c;
        }
    }
}

void querysub(vector<mint> &adds, int A, int B, mint x) {
    adds[A] += x;
    adds[B] -= x;
}

int main() {
    typedef StaticGraph<To> Graph;
    int N, R;
    scanf("%d%d", &N, &R);
    vector<vi> g(N);
    rep(i, N-1) {
        int x, y;
        scanf("%d%d", &x, &y), -- x, -- y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    tree_getorder(g, 0);
    vector<int> depth(N, 0);
    reu(ix, 1, N) {
        int i = t_ord[ix];
        depth[i] = depth[t_parent[i]] + 1;
    }
    vector<Graph::Edge> edges;
    reu(i, 1, N)
        edges.push_back(Graph::Edge(t_parent[i], i));
    Graph gg; gg.init(N, edges);
    SchieberVishkinLCA lca; lca.build(gg, 0);
    vector<mint> powRs(N*2+1);
    powRs[N] = 1;
    rer(i, 1, N) powRs[N+i] = powRs[N+i-1] * R;
    mint invR = mint(R).inverse();
    rer(i, 1, N) powRs[N-i] = powRs[N-i+1] * invR;
    const int T = 6;
    vector<mint> adds[T], coefs[T];
    rep(t, T) coefs[t].assign(N+1, mint());
    rep(i, N) {
        int d = depth[i];
        coefs[0][i] = powRs[N-d];
        coefs[1][i] = powRs[N+d];
        coefs[2][i] = powRs[N-d] * -d;
        coefs[3][i] = powRs[N+d] * +d;
        coefs[4][i] = powRs[N-d] * -d * -d;
        coefs[5][i] = powRs[N+d] * +d * +d;
    }
    rep(t, T) adds[t].assign(N+1, mint());
    vector<mint> values(N, mint());
    int U, Q;
    scanf("%d%d", &U, &Q);
    rep(ii, U) {
        int a1, d1, a2, d2, A, B;
        scanf("%d%d%d%d%d%d", &a1, &d1, &a2, &d2, &A, &B), -- A, -- B;
        //(a1 + z d1) (a2 + z d2) R^z
        //= a1 a2 R^z + (a1 d2 + d1 a2) z R^z + d1 d2 z^2 R^z
        int C = lca.query(A, B), Cp = C == 0 ? N : t_parent[C];
        int dA = depth[A], dB = depth[B], dC = depth[C];
        int uC = dA - dC, uB = dA + dB - dC * 2;
        mint p = powRs[N+dA], q = powRs[N-dB+uB];
        int e = -dB+uB;
        //a1 a2 R^z
        if(1) {
            mint t = mint(a1) * a2;
            querysub(adds[0], A, Cp, t * p);
            querysub(adds[1], B, C,  t * q);
        }
        //(a1 d2 + d1 a2) z R^z
        if(1) {
            mint t = mint(a1) * d2 + mint(d1) * a2;
            querysub(adds[2], A, Cp, t * p);
            querysub(adds[0], A, Cp, t * p * dA);
            querysub(adds[3], B, C,  t * q);
            querysub(adds[1], B, C,  t * q * e);
        }
        //d1 d2 z^2 R^z
        if(1) {
            mint t = mint(d1) * d2;
            querysub(adds[4], A, Cp, t * p);
            querysub(adds[2], A, Cp, t * p * dA * 2);
            querysub(adds[0], A, Cp, t * p * dA * dA);
            querysub(adds[5], B, C,  t * q);
            querysub(adds[3], B, C,  t * q * e * 2);
            querysub(adds[1], B, C,  t * q * e * e);
        }
    }
    rep(t, T) {
        for(int ix = N-1; ix > 0; -- ix) {
            int i = t_ord[ix];
            adds[t][t_parent[i]] += adds[t][i];
        }
        rep(i, N)
            adds[t][i] *= coefs[t][i];
//        cerr << t << ": "; rep(i, N) cerr << adds[t][i].get() << ", "; cerr << endl;
        rep(i, N)
            values[i] += adds[t][i];
        adds[t].assign(N+1, mint());
    }
//    cerr << "values: "; rep(i, N) cerr << values[i].get() << ", "; cerr << endl;
//    }
    vector<mint> sums = values;
    for(int ix = 1; ix < N; ++ ix) {
        int i = t_ord[ix];
        sums[i] += sums[t_parent[i]];
    }
    rep(ii, Q) {
        int A, B;
        scanf("%d%d", &A, &B), -- A, -- B;
        int C = lca.query(A, B);
        mint ans = 0;
        ans += sums[A];
        ans += sums[B];
        ans -= values[C];
        if(C != 0)
            ans -= sums[t_parent[C]] * 2;
        printf("%d\n", ans.get());
    }
    return 0;
}


Problem solution in 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;
}