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.
Edges of the tree:-
4 3 3 1 5 2 1 2
Values of nodes 1 to 5:-
1 10 4 9 4
- 1st second:-
Add(1,6). Add the value 6 to node 1.
- 2nd second:- What is the current value of node 3?
- 3rd second:-
- 4th second:-
- 5th second:-
- 6th second:-
- 7th second:-
- 8th second:-
- 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