How to answer multiple queries for a tree?

Question

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

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

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 p^th 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≤10⁵.

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:-

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

Expected Output

• 6
• 0
• 33
• 25

Explanation

• 1^st second: 6,1,1,13,14 (Values of all nodes)
• 2^nd second: 0,6,6,14,15
• 3^rd second: 0,0,5,20,21
• 4^th second: 0,0,0,25,21
• 5^th second: 0,2,0,25,21
• 6^th second: 0,0,0,25,33
• 7^th second: 0,0,0,25,33
• 8^th second: 0,0,0,25,33

Answer 1

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))$.