TREEUGH - Editorial

PROBLEM LINK:

Contest
Practice

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 :slight_smile:

SOLUTION:

Setter

Tester

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;
	}
}

Editorialist

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 :smiley:

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-

1 Like

Another interesting overkill solution is to use euler tour + lazy segment tree. It would be useful, if we were to handle queries and updates in mixed order. (Though got WA, solved with DFS).

lazy will be used, if there are queries, get sum of subtree at node i. Otherwise simple segment tree would work.

Still, haven’t been able to get all AC

1 Like

@sarthakmanna,isn’t it a straight forward euler tour+segment problem?

U could provide a link of your solution…

I tried the straight-forward approach without the Segment Trees, hoping for weak test cases. XD

1 Like

hoping for weak test cases
lol.

No dear xD. I made sure to try out brute force approaches and suggest TCs for some heuristic approaches as well :stuck_out_tongue:

Eg - Initially in DECUNI O(NQ) passed. Got 2 more TCs added :stuck_out_tongue:

1 Like

Considering the fact that diff[i] = arr[i]-arr[i-1], in each query why is v added to to diff[in[u]] and subtracted from diff[out[u]]?

in[u] and out[u] are the positions at which you enter and leave a node, right? Why would this correspond to its array’s value(ie: why would in[u]/out[u] be equal to arr[i] and arr[j], where all elements between arr[i] and[j] are within the query’s subtree?)

Ok, your doubt is in Euler tour. The thing is, nodes can be randomly labelled. So if you use diff[u] and diff[v], its possible that they dont make a valid range, or its also possible that some unwanted node gets updated just because its label is between those.

But when we do diff[in[u]], we ensure that only nodes after entering u get updated, and diff[out[u]] ensures that only nodes after leaving u get updated. Their difference updates the nodes where we reach after going in u but before coming out of u, which is u’s subtree.

But why would the range from in[u] to out[u] consist of all nodes in the subtree?

For example, in the sample test case provided, won’t the order in which the nodes are visited be - 1,3,5,[4,3],[2,1]? (the 3 and 1 is repeated as that will be its out position)

Out here if 3 is updated, the range is 2 to 4, however this range isn’t the same range that’s meant to correspond to it’s arr[i] values, as node 2 would be getting updated, while node 5 won’t, as diff[i] is based of arr[i], and not the euler tour’s position.

I’m sorry if I’m complicating this question, but this is confusing me :confused: