# Dynamic Summation

### Problem Statement :

```Given a tree of N nodes, where each node is uniquely numbered in between [1, N]. Each node also has a value which is initially 0. You need to perform following two operations in the tree.

Update Operation
Report Operation
Update Operation

U r t a b
Adds ab + (a+1)b + (b+1)a to all nodes in the subtree rooted at t, considering that tree is rooted at r (see explanation for more details).

Report Operation

R r t m
Output the sum of all nodes in the subtree rooted at t, considering that tree is rooted at r. Output the sum modulo m (see explanation for more details).

Input Format

First line contains N, number of nodes in the tree.
Next N-1 lines contain two space separated integers x and y which denote that there is an edge between node x and node y.
Next line contains Q, number of queries to follow.
Next Q lines follow, each line will be either a report operation or an update operation.

Output Format

For each report query output the answer in a separate line.

Constraints

1 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ m ≤ 101
1 ≤ r, t, x, y ≤ N
x ≠ y
1 ≤ a, b ≤ 1018

Notes

There will be at most one edge between a pair of nodes.
There will be no loop.
Tree will be completely connected.```

### Solution :

```                            ```Solution in C :

In   C++  :

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

typedef long long int LL;
typedef vector<int> VI;
typedef pair<int, bool> PIB;

const int N_MODS = 5;
const int MOD[N_MODS] =
{ 143601703, 235439621, 393965597, 523222925, 1010408256 };

LL modPow(LL b, LL e, int m) {
LL r = 1; b %= m;
while (e) {
if (e & 1) r = (r * b) % m;
b = (b * b) % m;
e >>= 1;
}
return r;
}

int gcd(int a, int b) {
while (b) {
a %= b; swap(a, b);
}
return a;
}

int extGCD(int a, int b, int &x, int &y) {
int nx, ny;
x = ny = 1;
y = nx = 0;

while (b) {
int q = a/b;
a -= q*b; swap(a, b);
x -= q*nx; swap(x, nx);
y -= q*ny; swap(y, ny);
}

return a;
}

// assumes m1, m2 rel. prime with small product
void combine(int &r1, int &m1, int r2, int m2) {
int x, y; extGCD(m1, m2, x, y);

r1 = r1*y*m2 + r2*x*m1;
m1 *= m2;

r1 %= m1;
if (r1 < 0) r1 += m1;
}

struct segtreeSumMod {
int n;
VI mem[N_MODS], prop[N_MODS];

segtreeSumMod(int n_) : n(n_) {
for (int i = 0; i < N_MODS; ++i) {
mem[i] = VI(2*n-3);
prop[i] = VI(2*n-3);
}
}

// mutable state vars (per outer call)
mutable int s, e;
mutable int inc[N_MODS];

void incRange(int s, int e, LL a, LL b, bool invert) {
for (int i = 0; i < N_MODS; ++i) {
LL val = modPow(a, b, MOD[i]) + modPow(a+1, b,
MOD[i]) + modPow(b+1, a, MOD[i]);
inc[i] = (int) (val % MOD[i]);
}

if (invert) {
this->s = 0; this->e = s; incRangeRec(0, n-2);
this->s = e; this->e = n-1; incRangeRec(0, n-2);
}
else {
this->s = s; this->e = e; incRangeRec(0, n-2);
}
}

void incRangeRec(int lo, int hi) {
int m = (lo + hi) / 2;
if (lo == hi) m += n-2;

LL len = intLen(lo, hi);
if (len) {
if ((s <= lo) && (hi+1 <= e))
incProps(m);
else if (lo < hi) {
incMems(m, len);
incRangeRec(lo, m); incRangeRec(m+1, hi);
}
}
}

void incProps(int z) {
for (int i = 0; i < N_MODS; ++i)
prop[i][z] = (prop[i][z] + inc[i]) % MOD[i];
}

void incMems(int z, LL mult) {
for (int i = 0; i < N_MODS; ++i)
mem[i][z] = (mem[i][z] + inc[i] * mult) % MOD[i];
}

VI sumRange(int s, int e, bool invert) const {
for (int i = 0; i < N_MODS; ++i)
inc[i] = 0;

if (invert) {
this->s = 0; this->e = s; sumRangeRec(0, n-2);
this->s = e; this->e = n-1; sumRangeRec(0, n-2);
}
else {
this->s = s; this->e = e; sumRangeRec(0, n-2);
}

return VI(inc, inc+N_MODS);
}

void sumRangeRec(int lo, int hi) const {
int m = (lo + hi) / 2;
if (lo == hi) m += n-2;

LL len = intLen(lo, hi);
if (len) {
if ((s <= lo) && (hi+1 <= e))
else if (lo < hi) {
sumRangeRec(lo, m); sumRangeRec(m+1, hi);
}

}
}

void addMems(int z) const {
for (int i = 0; i < N_MODS; ++i)
inc[i] = (inc[i] + mem[i][z]) % MOD[i];
}

void addProps(int z, LL mult) const {
for (int i = 0; i < N_MODS; ++i)
inc[i] = (inc[i] + prop[i][z] * mult) % MOD[i];
}

LL intLen(int lo, int hi) const {
int p = max(s, lo), q = min(e-1, hi);
return (p <= q) ? (q - p + 1) : 0;
}
};

struct modTrees {
int n;

VI pos, end;
vector<VI> children;
segtreeSumMod stats;

modTrees(int n_, const vector<VI> &g) : n(n_),
pos(n_), end(n_), children(n_), stats(n_+1)
{ dfs(g); }

int dfs(const vector<VI> &g, int v = 0, int cur = 0) {
pos[v] = cur++;
end[v] = pos[v] + 1;

for (auto i : g[v])
if (!end[i]) {
cur = dfs(g, i, cur);
end[v] = end[i];
children[v].push_back(i);
}

return cur;
}

bool isAOutsideB(int a, int b) const {
return (pos[a] < pos[b]) || (end[b] <= pos[a]);
}

int childPath(int start, int target) const {
int lo = 0, hi = (int) children[start].size();
while (hi-lo > 1) {
int m = (lo + hi) / 2;
int cm = children[start][m];
if (pos[cm] > pos[target])
hi = m;
else
lo = m;
}
return children[start][lo];
}

PIB subtreeRange(int r, int t) const {
if (r == t)
return PIB(0, false);
if (isAOutsideB(r, t))
return PIB(t, false);
return PIB(childPath(t, r), true);
}

void update(int r, int t, LL a, LL b) {
PIB z = subtreeRange(r, t);
stats.incRange(pos[z.first], end[z.first], a, b, z.second);
}

int report(int r, int t, int m) const {
PIB z = subtreeRange(r, t);

VI res = stats.sumRange(pos[z.first], end[z.first], z.second);

int ans = 0, mm = 1;
for (int i = 0; i < N_MODS; ++i) {
int g = gcd(MOD[i], m);
if (g > 1)
combine(ans, mm, res[i] % g, g);
}

return ans;
}
};

int main() {
ios_base::sync_with_stdio(false);

int n; cin >> n;

vector<VI> g(n);
for (int i = 0; i < n-1; ++i) {
int x, y; cin >> x >> y;
g[x-1].push_back(y-1);
g[y-1].push_back(x-1);
}

modTrees solver(n, g);

int q; cin >> q;
while (q--) {
char op; cin >> op;
if (op == 'U') {
int r, t; LL a, b; cin >> r >> t >> a >> b;
solver.update(r-1, t-1, a, b);
}
else {
int r, t, m; cin >> r >> t >> m;
cout << solver.report(r-1, t-1, m) << '\n';
}
}
}

In    Java  :

import java.io.*;
import java.util.*;

public class Solution {

PrintWriter out;
StringTokenizer st;
boolean eof;

static final int[] MODS =
{ 64, 81, 25, 49, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };
static final int LOG = 17;

List<Integer>[] g;
int[][] up;
int inTime;
int inOutTime;
int[] from;
int[] to;
int[] depth;

int[] enter, exit;
int[] sz;

void dfs(int v, int p, int curDepth) {
sz[v] = 1;
from[v] = inTime++;
enter[v] = inOutTime++;
up[v][0] = p;
depth[v] = curDepth;
for (int i = 1, prev = p; i < LOG; i++) {
prev = up[v][i] = up[prev][i - 1];
}
for (int to : g[v]) {
if (to != p) {
dfs(to, v, curDepth + 1);
sz[v] += sz[to];
}
}
to[v] = inTime - 1;
exit[v] = inOutTime++;
}

static int pow(int a, long b, int mod) {
int ret = 1;
for (; b > 0; a = a * a % mod, b >>= 1) {
if ((b & 1) == 1) {
ret = ret * a % mod;
}
}
return ret;
}

int eval(long a, long b, int mod) {
return (pow((int) (a % mod), b, mod)
+ pow((int) ((a + 1) % mod), b, mod) + pow(
(int) ((b + 1) % mod), a, mod)) % mod;
}

boolean isAnc(int v1, int v2) {
return enter[v1] <= enter[v2] && exit[v2] <= exit[v1];
}

int goUp(int v, int dist) {
for (int i = 0; dist > 0; i++, dist >>= 1) {
if ((dist & 1) == 1) {
v = up[v][i];
}
}
return v;
}

void solve() throws IOException {
int n = nextInt();
g = new List[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>(2);
}
up = new int[n][LOG];
for (int i = 0; i < n - 1; i++) {
int v1 = nextInt() - 1;
int v2 = nextInt() - 1;
}
from = new int[n];
to = new int[n];
enter = new int[n];
exit = new int[n];
sz = new int[n];
depth = new int[n];
dfs(0, 0, 0);

FenwickTree[] trees = new FenwickTree[MODS.length];
for (int i = 0; i < MODS.length; i++) {
trees[i] = new FenwickTree(n, MODS[i]);
}
int q = nextInt();

int[] addAll = new int[MODS.length];
int[] sumAll = new int[MODS.length];

while (q-- > 0) {
char type = nextToken().charAt(0);
if (type == 'U') {
int r = nextInt() - 1;
int v = nextInt() - 1;
long a = nextLong();
long b = nextLong();
int[] vals = new int[MODS.length];
for (int i = 0; i < MODS.length; i++) {
vals[i] = eval(a, b, MODS[i]);
}
int cntV;
if (v == r) {
cntV = n;
for (int i = 0; i < MODS.length; i++) {
addAll[i] = (addAll[i] + vals[i]) % MODS[i];
}
} else if (isAnc(v, r)) {
for (int i = 0; i < MODS.length; i++) {
addAll[i] = (addAll[i] + vals[i]) % MODS[i];
}
int ch = goUp(r, depth[r] - depth[v] - 1);
cntV = n - sz[ch];
for (int i = 0; i < MODS.length; i++) {
}
} else {
cntV = sz[v];
for (int i = 0; i < MODS.length; i++) {
}
}
for (int i = 0; i < MODS.length; i++) {
int delta = (int) ((long) cntV * vals[i] % MODS[i]);
sumAll[i] = (sumAll[i] + delta) % MODS[i];
}
} else {
int r = nextInt() - 1;
int v = nextInt() - 1;
int m = nextInt();
int[] vals = new int[MODS.length];
if (v == r) {
for (int i = 0; i < MODS.length; i++) {
vals[i] = sumAll[i];
}
} else if (isAnc(v, r)) {
for (int i = 0; i < MODS.length; i++) {
vals[i] = sumAll[i];
}
int ch = goUp(r, depth[r] - depth[v] - 1);
for (int i = 0; i < MODS.length; i++) {
vals[i] = (vals[i] - trees[i].get(from[ch], to[ch]) + MODS[i])
% MODS[i];
int delta = (int) ((long) sz[ch] * addAll[i] % MODS[i]);
vals[i] = (vals[i] - delta + MODS[i]) % MODS[i];
}
} else {
int cntV = sz[v];
for (int i = 0; i < MODS.length; i++) {
vals[i] = (vals[i] + trees[i].get(from[v], to[v]))
% MODS[i];
int delta = (int) ((long) cntV * addAll[i] % MODS[i]);
vals[i] = (vals[i] + delta) % MODS[i];
}
}
}
}
}

static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

static int getAnswer(int[] vals, int m) {
int[] gcds = new int[MODS.length];
for (int i = 0; i < MODS.length; i++) {
gcds[i] = gcd(MODS[i], m);
}
outer: for (int res = 0; res < m; res++) {
for (int i = 0; i < MODS.length; i++) {
if (res % gcds[i] != vals[i] % gcds[i]) {
continue outer;
}
}
return res;
}
throw new AssertionError();
}

static class FenwickTree {
private int n;
private int mod;

private int[] c0;
private int[] c1;

private int fix(int x) {
return (x % mod + mod) % mod;
}

public FenwickTree(int n, int mod) {
this.n = n;
this.mod = mod;
this.c0 = new int[n];
this.c1 = new int[n];
}

void add(int low, int high, int delta) {
/**
* [low, high]
*/
internalUpdate(low, -(low - 1) * delta, delta);
internalUpdate(high, high * delta, -delta);
}

private void internalUpdate(int x, int d0, int d1) {
d0 = fix(d0);
d1 = fix(d1);
for (int i = x; i < n; i |= i + 1) {
c0[i] = (c0[i] + d0) % mod;
c1[i] = (c1[i] + d1) % mod;
}
}

int get(int low, int high) {
/**
* [low, high]
*/
return fix(get(high) - get(low - 1));
}

int get(int x) {
/**
* [0, x]
*/
int a1 = 0;
int a0 = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
a1 = (a1 + c1[i]) % mod;
a0 = (a0 + c0[i]) % mod;
}
return (int) (((long) a1 * x + a0) % mod);
}
}

Solution() throws IOException {
out = new PrintWriter(System.out);
solve();
out.close();
}

public static void main(String[] args) throws IOException {
new Solution();
}

String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}

String nextString() {
try {
} catch (IOException e) {
eof = true;
return null;
}
}

int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}

long nextLong() throws IOException {
return Long.parseLong(nextToken());
}

double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}

In    C  :

#include <stdio.h>
#include <stdlib.h>
#define PNUM 26
#define MODNUM 5
typedef struct whatever{
long long offset;
long long val;
} node;
typedef struct _list{
int x;
struct _list *next;
} list;
void update(int r,int t,long long A,long long B);
void query(int r,int t,int m);
void s_sum_update(int n,int b,int e,int i,
int j,long long val,node*tree,int mod);
long long s_sum_query(int n,int b,int e,
int i,int j,long long offset,node*tree,int mod);
void insert_edge(int x,int y);
void dfs(int x,int level);
void dfs2(int x,int level);
int isA(int x,int y);
long long modPow(long long a,long long x,int mod);
int get_i(int*a,int num,int size);
int med(int*a,int size);
long long crt(long long *mod_prime,
long long *list,int size,long long P);
void ext_gcd(long long a,long long b,
long long *x,long long *y);
int prime[PNUM]={2, 3, 5, 7, 11, 13, 17,
19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101};
int pmod[MODNUM]={908107200, 247110827,
259106347, 1673450759, 72370439};
int p_idx[PNUM]=
{0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2,
2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4};
int b[100000],e[100000],trace[100000]={0},
idx[100000],level_size[100000]={0},l[100000],
N,sort_size=0;
int *level_x[100000]={0},*level_i[100000]={0};
list *table[100000]={0};
node tree[MODNUM][400000]={0};

int main(){
int Q,r,t,x,y,i;
long long A,B;
char str[2];
scanf("%d",&N);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1);
}
dfs(0,0);
for(i=0;i<N;i++)
if(level_size[i]){
level_x[i]=(int*)malloc(level_size[i]*sizeof(int));
level_i[i]=(int*)malloc(level_size[i]*sizeof(int));
level_size[i]=0;
}
for(i=0;i<N;i++)
trace[i]=0;
dfs2(0,0);
scanf("%d",&Q);
while(Q--){
scanf("%s",str);
if(str[0]=='U'){
scanf("%d%d%lld%lld",&r,&t,&A,&B);
update(r-1,t-1,A,B);
}
else{
scanf("%d%d%d",&r,&t,&x);
query(r-1,t-1,x);
}
}
return 0;
}
void update(int r,int t,long long A,long long B){
long long val,i,j;
for(i=0;i<MODNUM;i++){
val=(modPow(A,B,pmod[i])+modPow(A+1,B,pmod[i])+modPow(
B+1,A,pmod[i]))%pmod[i];
if(isA(t,r)){
s_sum_update(1,0,N-1,b[0],e[0],val,&tree[i][0],pmod[i]);
if(t!=r){
j=get_i(level_i[l[t]+1],b[r],level_size[l[t]+1]);
if(l[t]+1==l[r])
j=level_x[l[t]+1][j];
else
j=level_x[l[t]+1][j-1];
s_sum_update(1,0,N-1,b[j],e[j],pmod[i]-val,&tree[i][0],pmod[i]);
}
}
else
s_sum_update(1,0,N-1,b[t],e[t],val,&tree[i][0],pmod[i]);
}
return;
}
void query(int r,int t,int m){
int rprime_size=0,i,j;
long long mm[MODNUM],rprime[PNUM],rlist[PNUM],p=m;
if(m==1){
printf("0\n");
return;
}
for(i=0;i<MODNUM;i++)
if(isA(t,r)){
mm[i]=s_sum_query(1,0,N-1,b[0],e[0],0,&tree[i][0],pmod[i]);
if(t!=r){
j=get_i(level_i[l[t]+1],b[r],level_size[l[t]+1]);
if(l[t]+1==l[r])
j=level_x[l[t]+1][j];
else
j=level_x[l[t]+1][j-1];
mm[i]=(mm[i]-s_sum_query(1,0,N-1,b[j],e[j],
0,&tree[i][0],pmod[i])+pmod[i])%pmod[i];
}
}
else
mm[i]=s_sum_query(1,0,N-1,b[t],e[t],0,&tree[i][0],pmod[i]);
for(i=0;i<PNUM;i++)
if(m%prime[i]==0){
rprime[rprime_size]=1;
while(p%prime[i]==0){
p/=prime[i];
rprime[rprime_size]*=prime[i];
}
rlist[rprime_size]=mm[p_idx[i]]%rprime[rprime_size];
rprime_size++;
}
printf("%lld\n",crt(rprime,rlist,rprime_size,m));
return;
}
void s_sum_update(int n,int b,int e,int i,
int j,long long val,node*tree,int mod){
if(b>e||i>j||b>j||e<i)
return;
if(b>=i&&e<=j){
tree[n].offset=(tree[n].offset+val)%mod;
tree[n].val=(tree[n].val+(e-b+1)*val)%mod;
return;
}
s_sum_update(n*2,b,(b+e)/2,i,j,val,tree,mod);
s_sum_update(n*2+1,(b+e)/2+1,e,i,j,val,tree,mod);
tree[n].val=(tree[n*2].val+tree[
n*2+1].val+tree[n].offset*(e-b+1))%mod;
return;
}
long long s_sum_query(int n,int b,int e,
int i,int j,long long offset,node*tree,int mod){
if(b>e||i>j||b>j||e<i)
return 0;
if(b>=i&&e<=j)
return (tree[n].val+(e-b+1)*offset)%mod;
offset=(offset+tree[n].offset)%mod;
return (s_sum_query(n*2,b,(b+e)/2,i,j,
offset,tree,mod)+s_sum_query(n*2+1,(
b+e)/2+1,e,i,j,offset,tree,mod))%mod;
}
void insert_edge(int x,int y){
list *node;
node=(list*)malloc(sizeof(list));
node->x=x;
node->next=table[y];
table[y]=node;
node=(list*)malloc(sizeof(list));
node->x=y;
node->next=table[x];
table[x]=node;
return;
}
void dfs(int x,int level){
trace[x]=1;
b[x]=sort_size++;
list *node;
l[x]=level;
level_size[level]++;
for(node=table[x];node;node=node->next){
if(!trace[node->x])
dfs(node->x,level+1);
}
e[x]=sort_size-1;
return;
}
void dfs2(int x,int level){
trace[x]=1;
list *node;
level_i[level][level_size[level]]=b[x];
level_x[level][level_size[level]]=x;
level_size[level]++;
for(node=table[x];node;node=node->next){
if(!trace[node->x])
dfs2(node->x,level+1);
}
return;
}
int isA(int x,int y){
return b[x]<=b[y] && e[x]>=e[y];
}
long long modPow(long long a,long long x,int mod){
long long res = 1;
a%=mod;
while(x>0){
if(x%2)
res=res*a%mod;
a=a*a%mod;
x>>=1;
}
return res;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
long long crt(long long *mod_prime,
long long *list,int size,long long P){
long long i,x,y,ans=0;
for(i=0;i<size;i++){
ext_gcd(mod_prime[i],P/mod_prime[i],&x,&y);
while(y<0)
y+=P;
ans+=list[i]*y%P*(P/mod_prime[i])%P;
ans%=P;
}
return ans;
}
void ext_gcd(long long a,long long b,
long long *x,long long *y){
long long q,r,s,t;
if(!b){
(*x)=1;
(*y)=0;
return;
}
q=a/b;
r=a%b;
ext_gcd(b,r,&s,&t);
(*x)=t;
(*y)=s-q*t;
return;
}```
```

## Polynomial Division

Consider a sequence, c0, c1, . . . , cn-1 , and a polynomial of degree 1 defined as Q(x ) = a * x + b. You must perform q queries on the sequence, where each query is one of the following two types: 1 i x: Replace ci with x. 2 l r: Consider the polynomial and determine whether is divisible by over the field , where . In other words, check if there exists a polynomial with integer coefficie

## Costly Intervals

Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k. Specifically, let A = [A1, A2, . . . , An ] be an array of length n, and let be the subarray from index l to index r. Also, Let MAX( l, r ) be the largest number in Al. . . r. Let MIN( l, r ) be the smallest number in Al . . .r . Let OR( l , r ) be the bitwise OR of the

## The Strange Function

One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development. You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting

## Self-Driving Bus

Treeland is a country with n cities and n - 1 roads. There is exactly one path between any two cities. The ruler of Treeland wants to implement a self-driving bus system and asks tree-loving Alex to plan the bus routes. Alex decides that each route must contain a subset of connected cities; a subset of cities is connected if the following two conditions are true: There is a path between ever

## Unique Colors

You are given an unrooted tree of n nodes numbered from 1 to n . Each node i has a color, ci. Let d( i , j ) be the number of different colors in the path between node i and node j. For each node i, calculate the value of sum, defined as follows: Your task is to print the value of sumi for each node 1 <= i <= n. Input Format The first line contains a single integer, n, denoti

## Fibonacci Numbers Tree

Shashank loves trees and math. He has a rooted tree, T , consisting of N nodes uniquely labeled with integers in the inclusive range [1 , N ]. The node labeled as 1 is the root node of tree , and each node in is associated with some positive integer value (all values are initially ). Let's define Fk as the Kth Fibonacci number. Shashank wants to perform 22 types of operations over his tree, T