Recalling Early Days GP with Trees

                            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)