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("%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;
}
0 Comments