How to update nodes of a tree multiple times?

问题:

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

How to answer the queries efficiently?