Given the efforts you spend in documentation of the code, you shouldn’t be shy to share that link again and again. 
15 Likes
Let’s assume we had no updates, so answer to any query at time t on non-leaf vertex u will be the original value of that vertex v which is reached after moving t steps above u, and for a leaf vertex u, it will be sum of values of vertices on path from u to v.
Actually updates on a vertex u are needed to be handled in a similar way. But this way some updates can wrongly affect other queries. So there’s a need to do updates, then do some queries and then undo the updates.
So what’s the right order to handle queries and updates? After scratching your head a bit you will realize that dfs order serves this exact purpose.
For moving up the tree we can use binary lifting technique.
And for path sum queries we can use inclusion-exclusion by keeping two segment trees, both based on euler tours, one which stores entry values and other which stores exit values.
Also we need to add a path tree of q (No. of queries) nodes at top of root of the original tree.
https://www.codechef.com/viewsolution/27365890
Hence final complexity O((N + Q)logN).
4 Likes
I just used time - depth[v] as index of array and build the sum segment tree over it. Then just process the query based on nodes in DFS traversal order. Since at any time segment tree contains updates of the all ancestor of any node, hence query reduced to sum of 0-L for leaf nodes and L-L for non-leaf nodes . So it is like :
- On reaching any node n, add all updates queries of node n.
- Process all the answer queries for node n
- Recursively traverse all the children
- Once all children are processed then remove all the updates of the node n from the segment tree.
Solution Link.
5 Likes
I am not able to understand how we are handling subtree updates and point queries in case of leaf nodes.
Can someone please explain?
In the leaf case, the problem is also reduced to “subtree updates, point queries” in a tree. We can use the same method (as in my spoiler tag) to solve the “subtree updates, point queries” problem.
(That means we need to solve two “subtree updates, point queries”'s, one for leaf and one for non-leaf. The two problems use the same algorithm.)
3 Likes
Just by maintaining an extra chain of nodes of length q above the root node and updating the node which is at (depth - time) times above it will be sufficient (this way we always have a node whom we can update). For a non-leaf node, the value of the respective parent at (depth - time) is the answer and for a leaf node sum of all nodes in the path from leaf to node from (depth - time) is the answer. We can solve this online.
I doubt that it can be solved online this way!
The queries need to be processed in the dfs style else what you update going upwards will affect wrongly queries on other sub trees as well (since you are going up you have no control over which subtree the update was intended for and which subtrees actually query it).
Or may be I’m missing out something. Please clarify!
3 Likes
How will you know when to undo the updates if the queries are coming online?
Can Anybody Tell why in author implementation, in "add " function of fenwick tree, x += 5 is done?
@vijju123
I understand that initial bateria at node at depth d can be understood as some sort of an update performed at -d seconds at root, which can descended now on current node.
I understand how time minus depth plays a key role in adding up of bacteria descended.
I am still unable to understand how the above concepts fit into a segment array. The only thing I understand about segment tree is that it can update and query a range of locations.
Help me to fill in the vital information, please!
Edit: In the editorial example, if I look at node 11, all its ancestors - i.e. 1 and 4 occur to the left of 11 in the DFS.
@dardev If you look at the DFS order, you will find that every subtree in the original tree, is a continuous range or subarray of it. So, since update at a node would affect all nodes in its subtree, update is equivalent to range update (range corresponding to subtree). The range for updates on subtrees of 1 and 4 in this example will include 11 since it is in the subtree. Later when you query for 11, you will find sum of all previous updates on any of its ancestors.
2 Likes
Thank you for the reply @hemanth_1
I understand that we are doing DFS from root.
So - first I need to think in terms of a function that returns subtree for given node as a query?
I am unable to understand how to store queries and how to arrange the queries accordingly i.e. by i - dep(v), please help me to understand this…
Why in setter solution add function has call to add(r,-value) ?
Adding kj to all the nodes in the subtree of the j-th node. using general update in N nodes in segment tree and to clear it will take O(n). Then why did he use segment tree for that? Or if he use any other technique to update values to all the nodes in the subtree. please someone answer this.
I think you are confused about prefix sum related techniques.
You can read more about prefix sums & fenwick trees, that’ll also help you in understanding how O(log n) operations can be used to maintain prefix sums using segment trees.