Tree and Queries

general
1

How can i solve this problem.

I know i can do it with dfs but what if the tree is linear . Then the recursion depth can be about 10^5 causing stack overflow.

So please could explain the approach for doing this problem.

2

Hello japoorv,

I decided to answer as it is my one of the favourite question :stuck_out_tongue: .

First of all … We can use slower solution mentioned by you to solve this problem but this will certainly run out of time if the test data is prepared well …

You must be familiar with the Binary Indexed Tree data structure … I am assuming you know how to perform these two operation over the BIT .

  1. update a point or an index
  2. query a range for the sum

We can reduce our tree problem to the problem where we just need to use the above mentioned functions to handle the updates and queries over the tree .

So, how can we transform tree to an array, such as for a node x, all nodes from subtree of x to be a subarray of array?

The answer is yes. We can do this by properties of DFS search. Before reading on, make sure that you know what is discovery time and finish time in a DFS search. Let’s build 3 arrays now – discover[], representing nodes in order of their discover times (a node is as before in discover as it has a small discover time), begin[] = for a node, in which time it was discovered and end[] = what’s last time of a discovered node before this node finishes. For a subtree of x, all nodes in the subtree are nodes in discover from position begin[x] to end[x].

Example: suppose you have tree 1-5; 1-6; 6-7; 6-4; 4-2; 4-3

Discover is {1, 5, 6, 7, 4, 2, 3}.

begin is {1, 6, 7, 5, 2, 3, 4}.

end is {7, 6, 7, 7, 2, 7, 4}.

What’s subtree of node 6? elements of discover from position begin[6] to end[6]. In this case, from 3 to 7, so elements {6, 7, 4, 2, 3}. You can see it’s correct and take more examples if you want :slight_smile:

void dfs(int u,int lev=0){
 
	L[u]=lev;
	V[u]=true;
	in[u]=++cnt;	
	for(vector :: itr it=G[u].begin();it!=G[u].end();++it){
		if(!V[*it]){
			dfs(*it,lev+1);
		}
	}
	out[u]=cnt;	
}

Look at this fragment code carefully this is the only most beautiful trick which is used in this problem .

we are maintaining the IN time and OUT time for a given node. Now if you think carefully all the nodes which have their IN time in between the IN time and OUT time of some node U represents the subtree of node U . Read the above things so many times so that you are completely clear with the idea and my efforts does not go in vain :stuck_out_tongue: .

once you are clear with the above idea problem reduces to one array and the mentioned queries . here is the full code for this problem .

int n,q,c,x,y,i,cnt=0;
VI L,in,out,BIT,V;
VL arr;
vector G;
 
 
void update(int idx,int val){
	
	while(idx<=n){
		BIT[idx]+=val;
		idx+=(idx&(-idx));
	}
}
 
int query(int idx){
	int sum=0;	
	while(idx>0){
		sum+=BIT[idx];
		idx-=(idx&(-idx));
	}
	return sum;
}
 
void dfs(int u,int lev=0){
 
	L[u]=lev;
	V[u]=true;
	in[u]=++cnt;	
	for(vector :: itr it=G[u].begin();it!=G[u].end();++it){
		if(!V[*it]){
			dfs(*it,lev+1);
		}
	}
	out[u]=cnt;	
}
 
 
int main(){
 
	cin >> n >> q;
	G.resize(n+1);
	arr.resize(n+1);
	V.resize(n+1);
	L.resize(n+1);
	in.resize(n+1);
	out.resize(n+1);
	BIT.resize(n+1);	
	rep(i,1,n){
		cin >> x >> y;
		G[x].pb(y);
		G[y].pb(x);
	}
	rep(i,1,n+1)
		cin >> arr[i];
	dfs(1);
	rep(i,1,n+1){
		if(arr[i]==0)
			update(in[i],1);
	}
	while(q--){
 
		char ch;
		cin >> ch >> x;
		if(ch=='Q'){
			
			int ans=query(out[x]);
			ans-=query(in[x]-1);
			cout << ans <> y;
			if(arr[x]){
				arr[x]+=y;
				if(arr[x]==0){
					update(in[x],1);
				}
			}else{
				arr[x]+=y;
				if(arr[x]){
					update(in[x],-1);	
				}
			}		
		}
	}	
	return 0;
}
3 Likes
3

read whatever is provided below … you will find yourself learning some amazing stuff …

4

That was some awesome stuff … .! :smiley:

1 Like