0
$\begingroup$

I encountered an interesting problem based on tree-data-structure.

We are given a tree which has N nodes, with 1≤N≤105.

Time starts from second 1 and it continues for q seconds.

At each second, the value of each internal node is transferred to all of its child nodes. This happens with all the nodes, except leaf nodes.

Sometimes, at a given time p (seconds), we are asked to return the current value of node x.

There is this O(logN) approach: just find the pth ancestor of the given node x, and output its value.

A harder version of the same problem

Sometimes, at a given time p (seconds), we are asked to return the current value of node x, or we are said to update the value of node x to y.

How to solve this problem for q queries (seconds) efficiently, where 1≤q≤105.

Example

Input

N=5, q=8

Edges of the tree:-

4 3
3 1
5 2
1 2

Values of nodes 1 to 5:-

1 10 4 9 4

Queries:-

  • 1st second:- Add(1,6). Add the value 6 to node 1.
  • 2nd second:- What is the current value of node 3? (?,3)
  • 3rd second:- Add(3,5)
  • 4th second:- (?,3)
  • 5th second:- Add(2,2)
  • 6th second:- Add(5,10)
  • 7th second:- (?,5)
  • 8th second:- (?,4)

Expected Output

  • 6
  • 0
  • 33
  • 25

Explanation

  • 1st second: 6,1,1,13,14 (Values of all nodes)
  • 2nd second: 0,6,6,14,15
  • 3rd second: 0,0,5,20,21
  • 4th second: 0,0,0,25,21
  • 5th second: 0,2,0,25,21
  • 6th second: 0,0,0,25,33
  • 7th second: 0,0,0,25,33
  • 8th second: 0,0,0,25,33
$\endgroup$
6
  • $\begingroup$ I read this exact same problem before this week. Have you posted elsewhere? $\endgroup$ Oct 9, 2019 at 16:42
  • $\begingroup$ Yes, I did. I have solved this problem as well, but I haven't found a way to calculate answer for leaf nodes.. $\endgroup$ Oct 9, 2019 at 16:44
  • $\begingroup$ Do you mean for the harder version? I don't know the answer yet, but I recommend you to start thinking for the case where the tree is a single path (so it can be modeled with an array). It is very likely that an idea for the array version can be extended to a tree using some idea such as Heavy Light Decomposition. $\endgroup$ Oct 9, 2019 at 16:48
  • $\begingroup$ I have found the answer for array version already and sadly it doesn't help in the tree version, for the array version:- Answer is simple, nothing much to do, but did not work in tree due to branching. $\endgroup$ Oct 9, 2019 at 16:50
  • $\begingroup$ I added an answer, but didn't find a simple answer to the array version which can be extended to the tree version, maybe if you post your solution to the array version (in the question) we can craft a simpler solution to the tree version. $\endgroup$ Oct 9, 2019 at 17:23

1 Answer 1

2
$\begingroup$

For this problem I recommend to solve first for trees with simpler structures that can be generalized afterwards with data structures that run on top of trees (there are plenty of them).

Let's build an idea of what are the dynamics of the problem before jumping to the answer. We have the array A = [N0, N1, N2, N3]. An let's say after each second numbers at each position moves one step to the right. And in some place one number might change (in cases of queries). The initial array after the first second will look like A = [N0, N0, N1, N2]. If we are asked to change the value at position $2$ (indexed in base $0$) with value Q0 at the end of the first step, then the array will look like A = [N0, N0, Q0, N2]. After the following step the array will look like A = [N0, N0, N0, Q0]. We should be able to answer queries of the form: What is the value of position $i$ at this moment?

If there is a value at position $i$ at time $t$ we know this value will be at position $i+\delta$ at time $t+\delta$, unless it is overridden by some update. In the case it was overridden it must be the case that it happened on a position to the right of position $i$.

Supposed we are asked for the value at position $p$ at time $t$. Turning previous equations backwards, we are looking for the right-most position to the left of $p$ (let's call it $o$ from origin) such that an update originated there at time $t_o = t - (p - o)$. We say that for all positions in the array there was a simultaneous update at the beginning with initial values. Rewrite previous equation as: $t_o - o = t - p$. Notice that the problem is simpler now, for every update in position $o$ at time $t_o$ with value $v$ we store at this position the value $(t_o - o, v)$. For every query of the form ($p$, $t$) we should ask for the right-most position to the left of $p$ such that the first element is $t - p$ and return $v$ from such pair.

After every second add always an update in the root with current value, in order to always find the answer for every query. This idea can be implemented with a 2D Segment Tree. Complexity for every query an update will be $O(log^2 N)$.

To turn this idea into the tree case, just notice that:

  • right becomes the sub-trees.
  • left becomes the ancestor.
  • position becomes the height.

Decompose the tree in paths using Heavy Light Decomposition (HLD) and solve the same instance of the problem. Since HLD decompose every path from node $u$ to the root in $O(log N)$ paths each update/query complexity will be $O(log^3 N)$. Overall complexity will be $O((N + Q) log^3 (N+Q))$.

$\endgroup$
5
  • $\begingroup$ log^3 might give time-limit problems, wait I am adding the solution to array version as well, and do one correction, all values keep getting added at the end of array which you ignored...kinda... after the first second, array will be:-[n0,n0,n1,n2+n3] $\endgroup$ Oct 9, 2019 at 17:40
  • 1
    $\begingroup$ Addition is not a major concern, since you can query first and update with proper value then. You can remove the factor introduced by HLD in the following way: instead of doing point updates and path queries, do sub-tree updates and point queries. If you flat the tree using pre-order traversal sub-trees are continuous arrays. $\endgroup$ Oct 9, 2019 at 17:50
  • $\begingroup$ Using the subtree tricks, I solved the question, I am just not able t answer queries of leaf nodes, as they have sum of all the previous updates upto a particular time...may I share my solution of tree queries which solves every queries except leaf node queries.. ? $\endgroup$ Oct 9, 2019 at 17:51
  • $\begingroup$ Should I message you on Codeforces? $\endgroup$ Oct 9, 2019 at 17:53
  • $\begingroup$ Can you add your subtree approach to the problem in the answer as well ? $\endgroup$ Oct 9, 2019 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.