In this HackerRank Recalling Early Days GP with Trees problem solution, 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. You need to return the sum of the node values (S) lying in the path from node i to node j modulo 100711433.

HackerRank Recalling Early Days GP with Trees problem solution


Problem solution in Java Programming.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
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<>();
    queue.add(new Node(d, v, p));
    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) {
          queue.add(new Node(node.d+1, u, node.v));
        }
      }
    }
  }

  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<>();
    queue.add(new Node2(v, p));
    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<>();
    queue.add(new Node3(v, p, s));
    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 {
    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());
    r = Integer.parseInt(st.nextToken()) % MOD;
    invr = r > 0 ? inv(r) : 0;
    e = new List[n];
    for (int i = 0; i < n; i++) {
      e[i] = new LinkedList<>();
    }
    for (int i = 0; i < n-1; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken())-1;
      int v = Integer.parseInt(st.nextToken())-1;
      e[v].add(u);
      e[u].add(v);
    }
    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]];
      }
    }
    st = new StringTokenizer(br.readLine());
    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++) {
      st = new StringTokenizer(br.readLine());
      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]);
        d[v] = add(d[v], x);
        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 {
        d[v] = add(d[v], x);
      }
    }
    dfs2(0, -1);
    path = new long[n];
    dfs3(0, -1, 0);
    for (int i=0; i < q; i++) {
      st = new StringTokenizer(br.readLine());
      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();
  }  
}


Problem solution in C++ programming.

#define _CRT_SECURE_NO_WARNINGS
#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 <list>
#include <cassert>
#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
#define EPS 1e-9
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(x > y) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

struct CentroidPathDecomposition {
    vector<int> colors, positions;    //Vertex -> Color, Vertex -> Offset
    vector<int> lengths, parents, branches;    //Color -> Int, Color -> Color, Color -> Offset
    vector<int> parentnodes, depths;    //Vertex -> Vertex, Vertex -> Int
    //vector<...>????1???????????????sortNodes()??????
    vector<int> sortednodes, offsets;    //Index -> Vertex, Color -> Index

    //???????????????????????????(???)
    void build(const vector<vi> &g, int root) {
        int n = g.size();

        colors.assign(n, -1); positions.assign(n, -1);
        lengths.clear(); parents.clear(); branches.clear();
        parentnodes.assign(n, -1); depths.assign(n, -1);

        vector<int> subtreesizes;
        measure(g, root, subtreesizes);

        struct State {
            int i, len, parent;
            State() { }
            State(int i_, int l, int p): i(i_), len(l), parent(p) { }
        };
        depths[root] = 0;
        vector<State> s;
        s.push_back(State(root, 0, -1));
        while(!s.empty()) {
            State t = s.back(); s.pop_back();
            int i = t.i, len = t.len;
            int color = lengths.size();
            if(t.parent != -2) {
                assert(parents.size() == color);
                parents.push_back(t.parent);
                branches.push_back(len);
                len = 0;
            }
            colors[i] = color;
            positions[i] = len;

            int maxsize = -1, maxj = -1;
            each(j, g[i]) if(colors[*j] == -1) {
                if(maxsize < subtreesizes[*j]) {
                    maxsize = subtreesizes[*j];
                    maxj = *j;
                }
                parentnodes[*j] = i;
                depths[*j] = depths[i] + 1;
            }
            if(maxj == -1) {
                lengths.push_back(len + 1);
            }else {
                each(j, g[i]) if(colors[*j] == -1 && *j != maxj)
                    s.push_back(State(*j, len, color));
                s.push_back(State(maxj, len + 1, -2));
            }
        }

        sortNodes();
    }

    void sortNodes() {
        int n = colors.size(), m = lengths.size();
        sortednodes.resize(n, -1);
        offsets.resize(m + 1);
        rep(i, m) offsets[i+1] = offsets[i] + lengths[i];
        rep(i, n) sortednodes[offsets[colors[i]] + positions[i]] = i;
    }

    void get(int v, int &c, int &p) const {
        c = colors[v]; p = positions[v];
    }
    bool go_up(int &c, int &p) const {
        p = branches[c]; c = parents[c];
        return c != -1;
    }

    inline const int *nodesBegin(int c) const { return &sortednodes[0] + offsets[c]; }
    inline const int *nodesEnd(int c) const { return &sortednodes[0] + offsets[c+1]; }

private:
    void measure(const vector<vi> &g, int root, vector<int> &out_subtreesizes) const {
        out_subtreesizes.assign(g.size(), -1);
        vector<int> s;
        s.push_back(root);
        while(!s.empty()) {
            int i = s.back(); s.pop_back();
            if(out_subtreesizes[i] == -2) {
                int s = 1;
                each(j, g[i]) if(out_subtreesizes[*j] != -2)
                    s += out_subtreesizes[*j];
                out_subtreesizes[i] = s;
            }else {
                s.push_back(i);
                each(j, g[i]) if(out_subtreesizes[*j] == -1)
                    s.push_back(*j);
                out_subtreesizes[i] = -2;
            }
        }
    }
};


typedef int Vertex;
struct Graph {
    typedef std::pair<Vertex, Vertex> Edge;
    struct To {
        Vertex to;
    };

    int n, m;

    Graph(int n_, const std::vector<Edge> &edges):
        n(n_), m(edges.size()), tos(m+1), offsets(n+1, 0) {
        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]].to = edges[e].second;
    }

    inline const To *edgesBegin(int v) const { return &tos[offsets[v]]; }
    inline const To *edgesEnd(int v) const { return &tos[offsets[v+1]]; }

    inline const int outDegree(int v) const { return offsets[v+1] - offsets[v]; }

private:
    std::vector<To> tos;
    std::vector<int> offsets;
};
    
class SchieberVishkinLCA {
public:
    typedef unsigned Word;
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) {
        assert(g.m == g.n - 1);

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

        //euler tour
        Word currentIndex = 1;
        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 = 1;
        vertices.resize(g.n); vertices[0] = root;
        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????
        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);    //???????
        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 tree???LCA???????
        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 tree???I(x)???), I(x) = maxHIndices[x])
        //(hI(lca(v,u)) = j)?hI(v)?hI(u)????????????????????????…
        Vertex x, y;
        if(j == hIv) x = v;
        else {            //lca?v????????
            Word kMask = highestOneBitMask(ancestorHeights[v] & (j-1));    //v?????j???????????????????
            x = pathParents[(indices[v] & ~kMask | (kMask+1))-1];    //indices[v]?k???????????
        }
        if(j == hIu) y = u;
        else {            //lca?u????????
            Word kMask = highestOneBitMask(ancestorHeights[u] & (j-1));    //u?????j???????????????????
            y = pathParents[(indices[u] & ~kMask | (kMask+1))-1];    //indices[u]?k???????????
        }
        return indices[x] < indices[y] ? x : y;    //in-order????????????????????
    }
};

void direct_tree(const vector<vi> &g, int i, int parent, vector<pii> &out_edges) {
    each(j, g[i]) if(*j != parent) {
        out_edges.pb(mp(i, *j));
        direct_tree(g, *j, i, out_edges);
    }
}


template<int MOD>
struct ModInt {
    static const int Mod = MOD;
    int x;
    ModInt(): x(0) { }
    ModInt(signed sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; }
    ModInt(signed long long sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; }
    int get() const { return 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);
    }
    
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
typedef ModInt<100711433> mint;

mint powR[100001], powinvR[100001];
mint up[100001], down[100001];
mint sum[100001];
int main() {
    int N, R, invR, U, Q;
    scanf("%d%d", &N, &R);
    invR = mint(R).inverse().get();
    powR[0] = powinvR[0] = 1;
    reu(i, 1, N+1) powR[i] = powR[i-1] * R;
    reu(i, 1, N+1) powinvR[i] = powinvR[i-1] * invR;
    vector<vi> g(N);
    rep(i, N-1) {
        int a, b;
        scanf("%d%d", &a, &b); a --, b --;
        g[a].pb(b); g[b].pb(a);
    }
    vector<pii> edges;
    direct_tree(g, 0, -1, edges);
    CentroidPathDecomposition cpd; cpd.build(g, 0);
    SchieberVishkinLCA lca; lca.build(Graph(N, edges), 0);

    mset(up, 0); mset(down, 0);
    scanf("%d%d", &U, &Q);
    rep(ii, U) {
        int a, b, X;
        scanf("%d%d%d", &a, &b, &X); a --, b --;
        int l = lca.query(a, b);
        int c, p, lc, lp;
        cpd.get(l, lc, lp);
        mint x = X;
        cpd.get(a, c, p);
        while(1) {
            int k = cpd.offsets[c], kp = k + p, k0 = k + (c == lc ? lp : 0);
            up[k + p] += x;
            x *= powR[kp - k0 + 1];
            if(k0) up[k0 - 1] -= x;
            if(c == lc) break;
            cpd.go_up(c, p);
        }
        int len = cpd.depths[a] + cpd.depths[b] - cpd.depths[l] * 2;
        x = powR[len] * X;
        cpd.get(b, c, p);
        while(1) {
            int k = cpd.offsets[c], kp = k + p, k0 = k + (c == lc ? lp + 1 : 0);
            int h = kp - k0 + 1;
            mint nx = x * powinvR[h];
            down[k0] += nx * R;
            down[kp + 1] -= x * R;
            if(c == lc) break;
            x = nx;
            cpd.go_up(c, p);
        }
    }

    for(int i = N-1; i > 0; i --) up[i-1] += up[i] * R;
    for(int i = 0;   i < N; i ++) down[i+1] += down[i] * R;
    sum[0] = 0;
    rep(i, N) sum[i+1] = sum[i] + up[i] + down[i];
    rep(ii, Q) {
        int a, b;
        scanf("%d%d", &a, &b); a --, b --;
        int l = lca.query(a, b);
        int c, p, lc, lp;
        cpd.get(l, lc, lp);
        cpd.get(a, c, p);
        mint ans = 0;
        while(1) {
            int k = cpd.offsets[c], kp = k + p, k0 = k + (c == lc ? lp : 0);
            ans += sum[kp+1] - sum[k0];
            if(c == lc) break;
            cpd.go_up(c, p);
        }
        cpd.get(b, c, p);
        while(1) {
            int k = cpd.offsets[c], kp = k + p, k0 = k + (c == lc ? lp + 1 : 0);
            ans += sum[kp+1] - sum[k0];
            if(c == lc) break;
            cpd.go_up(c, p);
        }
        printf("%d\n", ans.get());
    }
    return 0;
}


Problem solution in 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
            {
                chain_head[cn] = x -> x;
                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;
    chain_head[0] = 0;
    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;
        x = DP[0][chain_head[node_chain[x]]];
    }
    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;
        ty = DP[0][chain_head[node_chain[ty]]];
    }
    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--;
        y = DP[0][chain_head[node_chain[y]]];
    }
    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;
        x = DP[0][chain_head[node_chain[x]]];
    }
    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;
}