Dynamic Summation

                            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))
addMems(m);
else if (lo < hi) {
sumRangeRec(lo, m); sumRangeRec(m+1, hi);
}

addProps(m, len);
}
}

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 {

BufferedReader br;
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;
g[v1].add(v2);
g[v2].add(v1);
}
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++) {
trees[i].add(from[ch], to[ch], -vals[i]);
}
} else {
cntV = sz[v];
for (int i = 0; i < MODS.length; i++) {
trees[i].add(from[v], to[v], vals[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];
}
}
out.println(getAnswer(vals, m));
}
}
}

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 {
br = new BufferedReader(new InputStreamReader(System.in));
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 {
return br.readLine();
} 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;
}