PROBLEM LINK:
Author: Abdullah768
Editorialist: Abdullah768
DIFFICULTY:
MEDIUM
PREREQUISITES:
Dfs, Fibonacci Numbers, Dynamic Programming
PROBLEM:
Given a rooted tree T (root = node 1) with N vertices (all containing value 0), Perform Q queries of the following type and output the final tree (nodes 1 to N).
U X A B: The character ‘U’ followed by 3 integers X A B
For each query, let f be defined as
f(1)=A
f(2)=B
f(i)=f(i-1)+f(i-2)
For every node on the path from root to X (both inclusive):
T[i]=T[i]+f[level(i)]
Where level of root node is 1.
EXPLANATION:
The problem does not require intermediate results, since we only need to calculate the final tree, we need to store some lazy values during update queries so that the final tree can be built by adding all queries at once.
The update queries are nothing but Fibonacci numbers with an offset (a,b). Kth term can be calculated as:
f(k)= afib(k)+bfib(k-1)
where fib represents the Fibonacci numbers starting with 0,1
Another observation that can be made is:
f(i)=f(i-1)+f(i-2)
therefore, f(i+2)=f(i+1)+f(i)
or, f(i)=f(i+2)-f(i+1)
At every node, 2 values can be stored previous and current.
During query:
Add depth(i)th term of the given sequence in the node’s ‘current’.
Add (depth(i)+1)th term of the given sequence in the node’s ‘previous’.
After all queries:
The value to be added at the parent node can be calculated as child’s ‘previous’– child’s ‘current’.
A node can have multiple children and hence the expression would be:
(C1Prev -C1cur)+(C2Prev-C2Cur)+(C3Prev-C3Cur)+……+(CnPrev-CnCur)
Which can be re written as:
(C1Prev+ C2Prev+C3Prev+……+CnPrev)-(C1Cur+ C2Cur+C3Cur+……+ CnCur)
Hence, a final Dfs can be done to do the above calculations in O(n)
AUTHOR’S SOLUTION:
Author’s solution Solution