HackerRank Recalling Early Days GP with Trees problem solution YASH PAL, 31 July 2024 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.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("%dn", 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("%lldn", ( 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; } coding problems solutions