Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/dynamic-summation/problem?isFullScreen=true
In this HackerRank in Data Structures -
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.
Sample Input
4
1 2
2 3
3 4
4
U 3 2 2 2
U 2 3 2 2
R 1 2 8
R 4 3 9
Sample Output
2
3
Explanation
Initially Values in each node : [0,0,0,0]
The first query is U 3 2 2 2. Here, tree is rooted at 3. It looks like
3(0)
/ \
/ \
2(0) 4(0)
|
|
1(0)
For the sub tree rooted at 2 ( nodes 2 and 1 ), we add ab + (a+1)b + (b+1)a = 22 + 32 + 32 = 22. After first update operation, nodes 1, 2, 3, and 4 will have values 22, 22, 0 and 0 respectively.
3(0)
/ \
/ \
2(22) 4(0)
|
|
1(22)
The second query is U 2 3 2 2. Here, tree is rooted at 2. It looks like
2(22)
/ \
/ \
1(22) 3(0)
|
|
4(0)
For the sub tree rooted at 3 (nodes 3 and 4), we add ab + (a+1)b + (b+1)a = 22 + 32 + 32 = 22. After second update operation, nodes 1, 2, 3, and 4 each have values 22,22,22,22 respectively.
2(22)
/ \
/ \
1(22) 3(22)
|
|
4(22)
The first report query is R 1 2 8 asks for the sum modulo 8 of the subtree rooted at 2, when the tree is rooted at 1. The tree looks like
1(22)
\
\
2*(22)
|
|
3*(22)
|
|
4*(22)
The sum of the values of nodes 2, 3 and 4 are
(22 + 22 + 22) % 8 = 2
The second report query is R 4 3 9 asks for the sum modulo 9 of the subtree rooted at 3 when the tree is rooted at 4. The tree looks like
4(22)
\
\
3*(22)
|
|
2*(22)
|
|
1*(22)
The sum of the values of nodes 3, 2 and 1 are
(22 + 22 + 22) % 9 = 3
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#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;
}