PROBLEM LINK:
Setter- Choudhury Istasis Mishra
Tester- Choudhury Istasis Mishra, Adhyyan Sekhsaria
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY
PRE-REQUISITES:
DFS OR Euler Tour+ Difference Array
PROBLEM:
Given a tree rooted at node 1, with each node having a value A_i, we have to find the value of each node after Q queries, where each query adds a value val to node u and all nodes in its subtree.
QUICK EXPLANATION:
There are 2 ways to solve this question.
First one is to, simply mark which node has been updated by the query and by how much. After processing all queries like this, run a DFS. Since we already have marked the required nodes, we know which nodes to update by what amount already.
The second way is, to run a Euler tour of the tree, and mark the time we enter and exit the sub-tree of every node. After this, we can use a difference array to process queries. Doing prefix sum of difference array restores the required array (by property of difference array) which gives us exact value of how much each node is updated in queries which lets us answer queries easily.
EXPLANATION:
There are two ways to solve this question. We will primarily discuss approach 1 which requires only DFS. The Euler Tour and difference array approach is slightly complicated, but its a nice introduction to the concept of difference arrays.
1. DFS Approach-
For this one, lets first ask what will brute force do? Brute force will go like, it will take the query, update all the nodes in node u's subtree by val using DFS, then take next query for new u and val, do another DFS, take new values of u adn val and so on.
Now, ask one thing - We only have to answer after ALL queries are processed. So do we really need to have the completely updated tree before that? No! What we can actually do is, just update node u and mark there that “Ok, I have to update its sub-tree by val when I run DFS.” Do this for all the queries.
Now, once all queries are done, run a single DFS. We can easily carry over updates of parent nodes to its subtree - in fact, we have to perform the exact same DFS which we were performing for every query in brute force. The only difference between a solution which passes subtask-1 (only) and the full solution is that the full solution runs DFS only after receiving all queries.
For implementation details, we can simply use the regular DFS function with slight modification. The usual DFS function for a tree is void DFS(int currNode, int parent) , we just have to change it to void DFS(int currNode, int parent, long long UpdatesFromParent) where UpdatesFromParent carries over the value which has to be updated because our currNode is in subtree of one-of-the updated nodes in query. You can refer to tester’s solution which uses this approach for full implementation, but remember to give it a try yourself first.
2. Difference Array and Euler Tour-
This is a complicated approach, and we will just brief over this. Please make sure that you goto pre-requisite link and learn about concept of difference array first.
In this approach, we first do a DFS after inputting the graph, and mark at what time we are entering a node u's subtree, and at what time we are exiting it. We can make 2 arrays, in[u] and out[u] where in[u] stores the time when we entered node u and its subtree, and out[u] stores when we exited it.
Obviously, the in[v] and out[v] of a node v which lies inside sub-tree of node u must be a value after we enter node u (i.e. after time in[u]) and before we exit the subtree of u (i.e. before time out[u]). In other words, for all nodes v in subtree of u, in[u] \le in[v] and out[u] \ge out[v].
Now, we follow the exact usage of difference array as given in link. Say, we have to update node u adn its subtree by a value val. Suppose our difference array is diff[]. We simply do the two steps-
diff[in[u]]+=v;//Mark all elements from [in[u],infinity] to be increased by v;
diff[out[u]]-=v;//Mark all elements from [out[u],infinity] to be reduced by v.
What is ultimately results in is, that value of all elements in range [in[u],out[u]) get updated by val. To get the complete array of update from difference array, we have to do a prefix-sum (Why?) and after that we get the exact values by which the nodes were updated. Now we can proceed to answer after all queries 
SOLUTION:
Setter
Click to view
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int> > g;
vector<ll> lazy;
void dfs(int cur, int par, ll sum){
//cout<<cur<<" "<<par<<" "<<sum<<endl;
lazy[cur] += sum;
for(int child: g[cur]){
if(child == par) continue;
dfs(child, cur, lazy[cur]);
}
}
int main(){
int n, q; cin>>n>>q;
g = vector<vector<int> >(n);
lazy = vector<ll>(n, 0);
vector<ll> init(n);
for(int i = 0; i < n; i++){
ll temp; cin>>temp;
init[i] = temp;
}
for(int i = 0; i < n-1; i++){
int u, v; cin>>u>>v; u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 0; i < q; i++){
int indx; ll val; cin>>indx>>val; indx--;
lazy[indx] += val;
}
dfs(0, -1, 0);
for(int i = 0; i < n; i++){
cout<<init[i] + lazy[i]<<endl;
}
}
Click to view
/*
*
********************************************************************************************
* AUTHOR : Vijju123 *
* Language: C++14 *
* Purpose: - *
* IDE used: Codechef IDE. *
********************************************************************************************
*
Comments will be included in practice problems if it helps ^^
*/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> arr[500005];
int arra[500005];
long long diff[2000000];
int timer=1,in[500005],out[500005];
void EulerDFS(int u,int par)
{
in[u]=timer++;
for(auto i:arr[u])
{
if(i!=par)
{
EulerDFS(i,u);
}
}
out[u]=++timer;
}
int main() {
// your code goes here
#ifdef JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int q,i,j;
cin>>n>>q;
for(i=1;i<=n;i++)cin>>arra[i];
int u,v;
for(i=0;i<n-1;i++)
{
cin>>u>>v;
arr[u].push_back(v);
arr[v].push_back(u);
}
EulerDFS(1,0);
/**We will use a difference array.
* The concept is simple. Dif[i] stores arr[i]-arr[i-1].
*/
while(q--)
{
cin>>u>>v;
diff[in[u]]+=v;//Mark all elements from [in[u],infinity] to be increased by v;
diff[out[u]]-=v;//Mark all elements from [out[u],infinity] to be reduced by v.
//After above two, only the nodes lying in subtree of u (i.e. those where we enter after u
//but exit before u) will be affected
}
//Now we need to get the original array in diff. This is done via prefix sum
for(int i=1;i<=timer;i++)
{
diff[i]+=diff[i-1];
}
for(int i=1;i<=n;i++)
{
cout<<diff[in[i]]+arra[i]<<" ";
}
cout<<endl;
return 0;
}
CHEF VIJJU’S CORNER 
1. Why prefix sum to restore array from difference array?
Click to view
Difference Array, is defined as diff[i]=arr[i]-arr[i-1]. What happens if we do a prefix sum?
Remember that diff[0]=arr[0]. Now, diff1=arr1-arr[0]. What if we do prefix sum? diff1=diff1+diff[0]=(arr1-arr[0])+arr[0]=arr1.
Similarly from mathematical induction we can claim that after prefix sum upto i’th index, diff[i]=arr[i]. If we can prove this for (i+1)'th index as well, this will get proved by principle of Mathematical Induction.
If we do diff[i+1]=diff[i+1]+diff[i], we get diff[i+1]=(arr[i+1]-arr[i])+arr[i]=arr[i+1]. Hence, proved that the difference array gets restored, i.e. diff[i]=arr[i] for all i after prefix sum.
2. Practice Problems-
- Sereja and Commands - Difference Arrays.
- Pishty and Tree - Euler Tour + Other
