TAQTREE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Tuan Anh
Tester: Gedi Zheng
Editorialist: Praveen Vaka and Praveen Dhinwa

DIFFICULTY:

Medium

PREREQUISITES:

graph theory, dfs order, heavy light decomposition

PROBLEM:

Given a weighted tree of N nodes. You have to perform following operations on it.

  • Update the weight of edge with new value c.
  • Find out the distance between node u and v.

QUICK EXPLANATION:

  • For solving subtask 1, You can use brute force solution by answering each query in O(N).

  • For solving subtask 2, you have to either use heavy light decomposition of tree or you can use dfs order property
    and maintain a segment tree/ binary indexed tree to answer the queries.

EXPLANATION:

Subtask 1

For solving subtask 1, you can simply use brute force. For that first we will do a dfs to find out parent child relationship.
Then using that information, we can find the LCA (Lowest Common Ancestor) of the tree in O(Height of Tree).
After finding LCA, we can divide the query into two parts and solve the two parts of the query individually in O(Height of Tree).

Time Complexity
So overall, each query will be performed in O(Height of Tree) which can be O(N) in the worst case. Note that if our tree is randomly
generated, then average height will be O(log N). But test cases were smartly designed to make sure to have O(N) in the worst case.

Subtask 2 (dfs order property Solution)

There is only one path (without repeating edges) between any two given nodes in a tree hence that is the shortest path.
For any two given nodes u and v this path will be the path from u to lca(u,v) followed by lca(u,v) to v or vice-versa.
So we have dist(u,v) = dist(root,u) + dist(root,v) - 2*dist(root, lca(u,v))

The lca information can be computed efficiently using the techniques mentioned here

So if we are able to compute the distance from root to any node efficiently under the changes of query type I we can solve this problem.

If we increase the cost of the edge (u,v) (u being closer to the root than v) by c then dist(root,x) is increased by c
for every x (including v) in the sub tree rooted at v. To solve this efficiently we will sort the nodes of the tree in the dfs
order and use a segment tree to increase the values of a range of numbers.

dfs order property
Note that in a dfs order the nodes of a sub tree always appear contiguously. Let us see this by an example.

Consider the following tree

1 → 5, 6, 7
5 → 2, 4, 8
6 → 3
7 → 13, 9
4 → 10, 11

If we write down the nodes in dfs order we will get
1, 5, 2, 4, 10, 11, 8, 6, 3, 7, 13, 9

We can see that the nodes of a sub tree always appear contiguously. So if we can keep track of the start and end point of the range for
a subtree we can update the ranges in our segment tree.

Let us make use of dfs order property
Let us maintain three two arrays start and end. start[u] will denote the position at which the node u lies in the dfs order.
end[u] will denote the index at which the sub tree rooted at u will end.

In the above example start[5] = 1 end[5] = 6 start[3] = 8 and end[3] = 8

Our segment tree will have n leaf nodes corresponding to the nodes of our tree in dfs order. Each leaf node will be storing the
initial distance from the root. All the internal nodes will have a value of zero.

When the value of an edge (u,v) (u being closer to the root) changes by an amount c in the type I query we ask the segment tree
to update this value for the whole range (start[v], end[v])

Here is the pseudo code of how we handle this

Input:
root: The current node in the segment tree which we are trying to update
LeftMin: the minimum leaf node that is part of the subtree at root
RightMax: the maximum leaf node that is part of the subtree at root
start: starting index of the range in the leaf level in segment tree.
end: ending index of the range in the leaf level in the segment tree.
update(root, leftMin, RightMax, start, end, c):
  if leftMin >= start && RightMax <= end:
    val[root] += c
  else:
    update(2*root, leftMin, (leftMin+RightMax)/2, start, end, c)
    update(2*root, (leftMin+RightMax)/2 + 1, RightMax, start, end, c)

When we get a type II query we compute dist(u,v) = dist(root,u) + dist(root,v) - 2*dist(root, lca(u,v))
dist(root, u) can be done using a simple get query on the segment tree.

Input:
u: The index of a leaf level in segment tree
Output: the distance of node corresponding to u from the root.
get(u):
  ans = val[u]
  while (u is not the root):
    u = parent(u)
    ans += val[u]
  return ans

Subtask 2 : Heavy Light Decomposition (HLD)

Assume that our tree is just a line, Then this problem can be easily solved using segment tree/ BIT.
We can maintain prefix sums of the array corresponding to the weights of the tree. This can be done using Binary Indexed Tree (BIT)
or Segment Tree in O(log n) time.
For learning BIT, you can check following topcoder tutorial.
For learning Segment tree, you can visit this awesome blog by Utkarsh Lath

If you can solve the problem for a chain using a segment tree, then there is a very good chance that you can solve
the problem for a tree using HLD. Indeed, if you make segment trees over the heavy edges, then the answer for your path X-Y
can be broken up into two paths from X to LCA(X, Y) and from Y to LCA(X, Y). Then, using that you make only logN shifts from one
heavy-chain to another, you are actually making only log(N) segment-tree queries.

Finding LCA is explained in previous part. I would just like to point out that you can make use of HLD to find LCA too.

The heavy-light decomposition is used to break up a Tree into s set of disjoint paths, with certain useful properties.
First, root the tree. Then, for each vertex x, we find the child of x having the largest subtree. Lets call that vertex y.
Then the edge x-y is a heavy edge, and all other x-child_vertex edges are light edges.

The most important property of this is, from any vertex x, the path from x to the root goes through at most logN different light-edges.
This is because, on this path, whenever you take a light edge, you are atleast doubling the size of the subtree rooted at the new vertex.
Hence you cannot perform this “doubling” effect more than logN times.

So now you can find HLD of the tree. Then you can maintain segment trees or BITs over the heavy edges.

For learning HLD in more details, You can read following awesome tutorial by Anudeep.

AUTHOR’S, TESTER’S and Editorialist’s SOLUTIONS:

setter
tester

Problems to Practice

Problems based on HLD.

Problems for faster LCA computation

Problems having dfs pre-order subtree idea

Please add more problems for practice !!

14 Likes
2

It can be solved by using LCA and + - DFS.For every edge a-b,you can attribute the value of the edge to a or b,depending on which one has the biggest level(we consider node 1 the root).So now we have updates on the nodes,not in the edges.From now it should be easy.The length of x-y path is (1-x + 1-y - 2* (1-lca(x,y)).1-x is the length of path from x to 1.Lca can be done with Euler and RMQ, + - DFS helps you in finding the length of path 1-x(for every x).Hope it will be helpful.Here is my solution CodeChef: Practical coding for everyone

1 Like
3

Solved it with sqrt-tree decomposition. Total complexity is O(Q*sqrt(N)). Each node can be skip-node, which contains dist to the parent skip-node. Skip-node is a regular node which height is divisible by sqrt(N).
Number of skip-nodes <= sqrt(N).

To process query of the first type we should maintain dist for the skip-nodes. To do that we should find all skip-nodes which has specified edge in the path to the parent skip-nodes and update their dist. It can be done by keeping reference to the skip nodes in one list. Complexity O(sqrt(N)).

To answer for query of the second type we should go up from both u and v until we get to the same skip-node. Once we find first skip-node on the way from the node to the top we can jump by parent skip nodes. Once we get to the same skip-node we should return back 1 step and go up node by node to not skip LCA. All time we move we should maintain current dist. It gives us complexity O(sqrt(N)).

Accepted solution

4

“Assume that our tree is just a line, Then this problem can be easily solved using segment tree/ BIT. We can maintain prefix sums of the array corresponding to the weights of the tree.”
I did not understand how the tree is being considered as a line. Could someone elaborate further?

5

Hello ajs97 …

look at this …

This discussion is not specific to this particular problem .

but this is useful in many problems …

here are the links to some more problems

and even more …

I decided to answer as it is my area of interest :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;
}
4 Likes
6

Someone please explain why this gets TLE?
https://www.codechef.com/viewsolution/18729285

7

does anyone know anything about the solution to this problem using self balancing bst ??

8

Actually I was trying the same approach, using AVL. but couldn’t give time to this problem during contest…