# 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