HackerRank Easy Addition problem solution YASH PAL, 31 July 2024 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. 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("%dn", 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("%lldn", ans); } return 0; } coding problems data structure