Problem Link:
Difficulty:
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
