# How to solve following tree problem with number assigned to each node? I have a tree whose nodes have numbers assigned to them initially. A series of $$Q$$ queries are asked from $$n=0$$ to $$n=Q-1$$ seconds. During end of each second numbers on a node (which are not leaf) are removed and gets transferred to each direct child node. Numbers on leaf node remain as it is and number coming from parent gets added to them. At each query it is possible that new number is added to a node. How to solve this efficiently?

Example: Suppose I have a tree 1—–2——3——-4 (1 is parent). Suppose at beginning numbers on nodes are 1, 2, 3, 4 respectively. Then at…

At zero second end 5 is added to node zero. At end of 0 seconds numbers on node are 5, 1, 2, 7. (Note 1 is not added to 5 because it is removed).

At one second end, 1 is added to node 4, then numbers are 0, 5, 1, 10. Fourth node has number 10 since it received 2 from parent node and 1 is added and 7 was present on it.

Now suppose at two second end, I am asked to tell number on 2nd node?Answer is 0.

I mean that in each query either a number can be added on a node or a question can be asked like – what is number on $$ith$$ node?
How to solve this in less than $$O(nQ)$$. Where $$n$$ is number of nodes and $$Q$$ is number of queries? Posted on Categories proxies