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 :



title-img 


                            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;
while (tail < head){
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[x][0], s);
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{
add(GP[x][0], s);
}
}

for (head=N-1;head>=0;head--){
x = Q[head];
for (i=0;i<G[x].size();i++){
y = G[x][i];
if (Depth[y] > Depth[x]){
add(GP[x][0],GP[y][0]*R);
add(GP[x][1],GP[y][1]*IR);
}
}
}

for (head=0;head<N;head++){
x = Q[head];
add(sum[x],GP[x][0]+GP[x][1]);
for (i=0;i<G[x].size();i++){
y = G[x][i];
if (Depth[y] > Depth[x]) add(sum[y],sum[x]);
}
}

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;
int x = 63-Long.numberOfLeadingZeros(n);
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){
int b = is.read();
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;

private static int readByte()
{
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);
b = readByte();
}
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;
b = readByte();
}
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;
while((b = readByte()) != -1 
&& !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

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

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

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

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 = []
       
    def add(self, neighbor):
        self.neighbors.append(neighbor)
    
    def __str__(self):
        return "(" + str(self.data) + ", " + str(self.parent) + ")"
    
def path(a, b):
    s = set()
    q = [[b]]
    s.add(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:
                s.add(n)
                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())
    nodes[a - 1].add(b - 1)
    nodes[b - 1].add(a - 1)
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)








View More Similar Problems

Sparse Arrays

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun

View Solution →

Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu

View Solution →

Print the Elements of a Linked List

This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode

View Solution →

Insert a Node at the Tail of a Linked List

You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty. Input Format: You have to complete the SinglyLink

View Solution →

Insert a Node at the head of a Linked List

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

View Solution →

Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

View Solution →