# Recalling Early Days GP with Trees

### Problem Statement :

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.

The update query is of the format

i j X
This means you'd have to add a GP series to the nodes which lie in the path from node i to node j (both inclusive) with first term of the GP as X on node i and the common ratio as R (given in the input)

The retrieval query is of the format

i j

You need to return the sum of the node values (S) lying in the path from node i to node j modulo 100711433.

Input Format

The first line contains two integers (N and R respectively) separated by a space.
In the next N-1 lines, the ith line describes the ith edge: a line with two integers a b separated by a single space denotes an edge between a, b.
The next line contains 2 space separated integers (U and Q respectively) representing the number of Update and Query operations to follow.
U lines follow. Each of the next U lines contains 3 space separated integers (i,j, and X respectively).
Each of the next Q lines contains 2 space separated integers, i and j respectively.

Output Format

It contains exactly Q lines and each line containing the answer of the ith query.

Constraints

2 <= N <= 100000
2 <= R <= 109
1 <= U <= 100000
1 <= Q <= 100000
1 <= X <= 10
1 <= a, b, i, j <= N

### Solution :

Solution in C :

In   C++  :

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

const int fold = 16;
const long long mod = 100711433;
long long R,IR;
vector<int> G[100001];
long long GP[100001][2],sum[100001];
int N,P[100001][fold+1],
Q[100001],Depth[100001]; bool chk[100001];

void mult(long long &a, long long b)
{a = a * b % mod;}
void add(long long &a, long long b)

{a = (a + b + mod) % mod;}

long long gpow(long long a, long long p)
{
long long r = 1;
while (p){
if (p & 1) mult(r,a);
mult(a,a);
p >>= 1;
}
return r;
}

int up(int x, int d)
{
int i;
for (i=fold;i>=0;i--) if (d & (1 << i)){
x = P[x][i];
d ^= 1 << i;
}
return x;
}

int commonancestor(int x, int y)
{
if (Depth[x] > Depth[y]) return commonancestor(y,x);
if (Depth[x] < Depth[y]){
y = up(y,Depth[y]-Depth[x]);
return commonancestor(x,y);
}
if (x == y) return x;

int i;
for (i=fold;i>=0;i--){
if (P[x][i] != P[y][i]){
x = P[x][i];
y = P[y][i];
}
}

return P[x][0];
}

int main()
{
int i,j,x,y,z;

scanf ("%d %lld",&N,&R);
R %= mod;
IR = gpow(R,mod-2);
for (i=1;i<N;i++){
scanf ("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}

int head = -1, tail = -1;
Q[++head] = 1; chk[1] = 1;
x = Q[++tail];
for (i=0;i<G[x].size();i++){
y = G[x][i];
if (chk[y] == 0){
Q[++head] = y; chk[y] = 1;
Depth[y] = Depth[x] + 1;

P[y][0] = x;
for (j=1;j<=fold;j++) if (P[y][j-1]){
P[y][j] = P[P[y][j-1]][j-1];
}
}
}
}

int U,M;
scanf ("%d %d",&U,&M);
while (U--){
long long s;
scanf ("%d %d %lld",&x,&y,&s);
z = commonancestor(x,y);
if (R){
long long left = gpow(R,Depth[x]-Depth[z]);
long long right = gpow(R,Depth[y]-Depth[z]);
add(GP[y][1], s * left % mod * right % mod);
add(GP[z][1], -((s * left) % mod));
if (P[z][0]) add(GP[P[z][0]][0], -((s * left % mod * R) % mod));
}
else{
}
}

for (i=0;i<G[x].size();i++){
y = G[x][i];
if (Depth[y] > Depth[x]){
}
}
}

for (i=0;i<G[x].size();i++){
y = G[x][i];
}
}

while (M--){
scanf ("%d %d",&x,&y);
z = commonancestor(x,y);
printf ("%lld\n",(sum[x]+sum[y]-sum[z]*2+GP[z][0]+GP[z][1]+mod*2)%mod);
}

return 0;
}

In   Java :

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";

static void solve()
{
int mod = 100711433;
int n = ni();
long R = ni();
int[] from = new int[n-1];
int[] to = new int[n-1];
for(int i = 0;i < n-1;i++){
from[i] = ni()-1;
to[i] = ni()-1;
}

int[][] g = packU(n, from, to);
int[] up = new int[n];
int[] down = new int[n];
int[][] pars = parents3(g, 0);
int[] par = pars[0], ord = pars[1], dep = pars[2];
int[][] spar = logstepParents(par);

int u = ni();
int Q = ni();
if(R % mod != 0){
for(int i = 0;i < u;i++){
int f = ni()-1, t = ni()-1, x = ni();
int lca = lca2(f, t, spar, dep);
//                tr(f, t, x, lca);

up[f] += x;
if(up[f] >= mod)up[f] -= mod;

int inter = (int)(x * pow(R, dep[f]
- dep[lca], mod) % mod);
if(par[lca] != -1){
int xin = (int)(inter * R % mod);
up[par[lca]] += mod - xin;
if(up[par[lca]] >= mod)up[par[lca]] -= mod;
}

int last = (int)(inter * pow(R,
dep[t] - dep[lca], mod) % mod);
down[lca] += mod - inter;
if(down[lca] >= mod)down[lca] -= mod;
down[t] += last;
if(down[t] >= mod)down[t] -= mod;
}

for(int i = n-1;i >= 0;i--){
int cur = ord[i];
int under = 0;
for(int e : g[cur]){
if(e != par[cur]){
under += up[e];
if(under >= mod)under -= mod;
}
}
up[cur] = (int)((up[cur] + under * R) % mod);
}

long IR = invl(R, mod);
for(int i = n-1;i >= 0;i--){
int cur = ord[i];
int under = 0;
for(int e : g[cur]){
if(e != par[cur]){
under += down[e];
if(under >= mod)under -= mod;
}
}
down[cur] = (int)((down[cur] + under * IR) % mod);
}

for(int i = 0;i < n;i++){
int cur = ord[i];
up[cur] += down[cur];
if(up[cur] >= mod)up[cur] -= mod;
for(int e : g[cur]){
if(e != par[cur]){
up[e] += up[cur];
if(up[e] >= mod)up[e] -= mod;
}
}
}
}else{
for(int i = 0;i < u;i++){
int f = ni()-1, t = ni()-1, x = ni();
up[f] += x;
if(up[f] >= mod)up[f] -= mod;
}
for(int i = 0;i < n;i++){
int cur = ord[i];
for(int e : g[cur]){
if(e != par[cur]){
up[e] += up[cur];
if(up[e] >= mod)up[e] -= mod;
}
}
}
}
for(int i = 0;i < Q;i++){
int f = ni()-1, t = ni()-1;
int lca = lca2(f, t, spar, dep);
long ret = up[f] + up[t] + mod - up[lca];
if(par[lca] != -1)ret += mod - up[par[lca]];
out.println(ret%mod);
}
}

public static long invl(long a, long mod)
{
long b = mod;
long p = 1, q = 0;
while(b > 0){
long c = a / b;
long d;
d = a; a = b; b = d % b;
d = p; p = q; q = d - c * q;
}
return p < 0 ? p + mod : p;
}

public static long pow(long a, long n, long mod)
{
//        a %= mod;
long ret = 1;
for(;x >= 0;x--){
ret = ret * ret % mod;
if(n<<63-x<0)ret = ret * a % mod;
}
return ret;
}

public static int lca2(int a, int b, int[][] spar, int[] depth)
{
if(depth[a] < depth[b]){
b = ancestor(b, depth[b]-depth[a], spar);
}else if(depth[a] > depth[b]){
a = ancestor(a, depth[a]-depth[b], spar);
}

if(a == b)return a;
int sa = a, sb = b;
for(int low = 0, high = depth[a],
t = Integer.highestOneBit(high),
k = Integer.numberOfTrailingZeros(t);
t > 0;t>>>=1,k--){
if((low^high) >= t){
if(spar[k][sa] != spar[k][sb]){
low |= t;
sa = spar[k][sa]; sb = spar[k][sb];
}else{
high = low|t-1;
}
}
}
return spar[0][sa];
}

protected static int ancestor(int a,
int m, int[][] spar)
{
for(int i = 0;m > 0 && a != -1;m>>>=1,i++){
if((m&1)==1)a = spar[i][a];
}
return a;
}

public static int[][] logstepParents(int[] par)
{
int n = par.length;
int m = Integer.numberOfTrailingZeros(
Integer.highestOneBit(n-1))+1;
int[][] pars = new int[m][n];
pars[0] = par;
for(int j = 1;j < m;j++){
for(int i = 0;i < n;i++){
pars[j][i] = pars[j-1][i] == -1 ? -1 : pars[j-1][pars[j-1][i]];
}
}
return pars;
}

public static int[][] parents3(int[][] g, int root)
{
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);

int[] depth = new int[n];
depth[0] = 0;

int[] q = new int[n];
q[0] = root;
for(int p = 0, r = 1;p < r;p++) {
int cur = q[p];
for(int nex : g[cur]){
if(par[cur] != nex){
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] {par, q, depth};
}

static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for(int f : from)
p[f]++;
for(int t : to)
p[t]++;
for(int i = 0;i < n;i++)
g[i] = new int[p[i]];
for(int i = 0;i < from.length;i++){
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}

public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty()
? System.in : new ByteArrayInputStream(
INPUT.getBytes());
out = new PrintWriter(System.out);

solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}

private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;

while(lptr < lenbuf)
if(!isSpaceChar(inbuf[lptr++]))
return false;

try {
is.mark(1000);
while(true){
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}

private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;

{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); }
catch (IOException e)

{ throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private static boolean isSpaceChar(int c)
{ return !(c >= 33 && c <= 126); }
private static int skip()
{ int b; while((b = readByte())
!= -1 && isSpaceChar(b)); return b; }

private static double nd()
{ return Double.parseDouble(ns()); }
private static char nc()
{ return (char)skip(); }

private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
}
return sb.toString();
}

private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private static int ni()
{
int num = 0, b;
boolean minus = false;
&& !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static long nl()
{
long num = 0;
int b;
boolean minus = false;
&& !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static void tr(Object... o)
{ if(INPUT.length() != 0)
System.out.println(Arrays.deepToString(o)); }
}

In    Python3 :

class Node():
def __init__(self, data):
self.data = data
self.neighbors = []

self.neighbors.append(neighbor)

def __str__(self):
return "(" + str(self.data) + ", " + str(self.parent) + ")"

def path(a, b):
s = set()
q = [[b]]
i = 0
while i < len(q):
p = q[i]
if p[0] == a:
return p
for n in nodes[p[0]].neighbors:
if n not in s:
q.append([n] + p)
i += 1
raise Exception

n, r = map(int, input().split())
nodes = [Node(0) for _ in range(n)]
for _ in range(n - 1):
a, b = map(int, input().split())
u, q = map(int, input().split())
for _ in range(u):
i, j, x = map(int, input().split())
for asdf in path(i - 1, j - 1):
node = nodes[asdf]
node.data += x
x *= r
for _ in range(q):
i, j = map(int, input().split())
print(sum(nodes[node].data for node in path(i - 1, j - 1)) % 100711433)

## Jenny's Subtrees

Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .

## Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty