Practice

Contest

Simple

Pre-requisites:

dfs, range sum queries

Problem:

You are given a rooted tree T, associate with each vertex v a weight skill[v]. Also given are a set of queries of either the form “update skill of v to x”, or “what is the sum of skill values of vertices in the subtree of v”. For each query of the second form, return the answer.

Quick Explanation:

Map the given vertex numbers to [1…N] such that the subtree rooted at any vertex has all mapped values in a contiguous range. Then updates of the first form imply changing skill-values at the given mapped number, and queries of the second form are simply range sum queries in the appropriate range, that can be answered using either a segment tree or a binary indexed tree.

The mapping of vertices that satisfy the given property can be done using dfs numbers (in-times/out-times). For details, see the Explanation section which draws an analogy to a bracketed expression.

Overall time complexity:
O(N) - finding out the mapping and the required range for each node
O(M logN) - to carry out each query: either point update, or range sum query.

Detailed Explanation:

For an illustration, let us consider the following tree:

``````
1
/ \
2   5
/ \
3   6
\
4

``````

From the above, I can form a bracketed expression of the form:

``````(x1 + (x2) + (x5 + (x3 + (x4)) + (x6)))
``````

Whenever I go down the tree, I am opening a bracket, whenever I go up the tree, I am closing a bracket. I am also giving “variables” that will correspond to skill-values for each node.

Seeing the above, I can rewrite 1,2,3,4,5 by mapping them to values as seen from left to right:

``````1 -> 1
2 -> 2
5 -> 3
3 -> 4
4 -> 5
6 -> 6
``````

Now, in the mapped version, the bracketed expression looks like:

``````(y1 + (y2) + (y3 + (y4 + (y5)) + (y6)))
``````

We are here interested in queries of two types:
Type1: change value of x[i], or in other words, y[mapped(i)]
Type2: Find the total in the complete bracket “defined” by i, which is y[mapped(i)] + y[mapped(i)+1] + … + y[end_range(i)], for suitable mapped(i) and end_range(i).

The good thing to note is, type2 is now a query over values in a range. This can be done by a segment tree or a binary indexed tree! We only need what the range is, given each vertex.

Finding out the range, as well as the mapping, can be done easily by dfs-times. The dfs-time for a node is the value of a time-counter when that node was visited. Indeed, if you ran a dfs on the given tree, it will visit the nodes in the order “1-2-5-3-4-6” itself! The range is then just starting from the current point, and ending at the latest time a node was visited. This information can be returned in the dfs function, as in the following pseudocode:

``````
int dfs(node v, int time)
mapping[v] = time
ret = time
for(c is a child of v)
ret = dfs(c, ret+1)	//give it the next "time"-point, and get the latest time point of the child for future
begin_range[v] = time
end_range[v] = ret
return ret

``````

Calling the above with dfs(1, 1) will do all the magic for you!

Finally, a BIT pseudocode implementation of the rest of the problem:

``````void update(int S, int x)
BIT.increment(mapping[S], x - skill[S])
skill[S] = x;

int query(int S)
return BIT.query(end_range[S]) - BIT.query(begin_range[S]-1)
``````

Alternate Approach:

This approach was used by some contestants. It is summarized as follows:

Step 1: Perform a heavy-light decomposition of the tree.
Step 2: Initialize each node with the value that is the sum of the skill-levels of its subtree.
Step 3: For each “U S x” query, add “skill[S]-x” to the nodes along the path from S to the root. Due to Heavy-light decomposition structure, this can be done in O(logN ^ 2) time. Also update the value of skill[S].
Step 4: For each “Q S” query, return the value stored in the node S.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

10 Likes

Can someone help me to describe what that sentence from problem statement means?

This is then followed by N-1 lines consisting of pairs of integers (u, v), denoting that either u is an immediate superior of v, or vice-versa.

It seems to me that not always u is parent of v in input. How did you solved this? It seems that I had problem with input reading, any idea where I’m wrong?

http://www.codechef.com/viewsolution/2291525

5 Likes

I’m not able to figure out, why my solution is judged as wrong…

http://www.codechef.com/viewsolution/2291780

http://www.codechef.com/viewsolution/2292712

Great Problem! Fun to learn new stuff!

What does it mean to skip in HL decomposition as mentioned in the editorial link?

It is a more general method to solve this kind of problem. However it requires longer code as well as slow down the solution.

Another BIT question seems like codechef has a thing about them.

Can anyone tell me what’s wrong with my code?
https://www.codechef.com/viewsolution/16081419

Tried the Alternate approach mentioned in this post, still not working. Ending up in Wrong Answer. Can someone let me know what’s wrong in this approach ?

https://www.codechef.com/viewsolution/16086366

What if I take simple tree instead of segment tree , for skillset i am taking seperate array, for update with reference to tree I am making updates in all nodes which are ancestors of given node, I don’t understand, why my approach is not working :- https://www.codechef.com/viewsolution/16093051 can anyone help me??

@betlista, regarding pairs (u, v), you can think of it as an edge exists between u and v. That, along with the fact that “1” is the ancestor of all nodes, will give us who is the immediate superior of whom.

Think of it this way. If you are given the pair (2, 1), you will know that 2 can’t be the superior of 1 - 1 has to be the superior of 2. If you also get something like (3, 2) later, you will know that 2 is the superior of 3, because 2’s superior is already determined to be 1. This can be done for all the nodes.

1 Like

The problem statement has mentioned: "This is then followed by N-1 lines consisting of pairs of integers (u, v), denoting that either u is an immediate superior of v, or vice-versa.
You simply start a DFS at the root of the tree (node 1 = Tywins, since All soldiers will have soldier 1 (Tywin) as their superior) to figure out, who is the superior of who.

2 Likes

any links to similar problems on spoj etc.?