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

We are given a tree which has

Nnodes, with1≤N≤10.^{5}Time starts from second 1 and it continues for

qseconds.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 nodex.

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 nodex,orwe are said to update the value of nodextoy.

How to solve this problem for *q* queries (seconds) efficiently, where *1≤q≤10 ^{5}*.

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