graph theory, dfs order, heavy light decomposition
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.
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.
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).
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 = 1 end = 6 start = 8 and end = 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.
AUTHOR’S, TESTER’S and Editorialist’s SOLUTIONS:
Problems to Practice
Problems based on HLD.
Problems for faster LCA computation
Problems having dfs pre-order subtree idea
- Propogating Tree Codeforces
- Blood Cousins Codeforces
- IIT Kanpur Monthly Programming Contest 1: Problem Tree and Queries
Please add more problems for practice !!