Can you please add a little explanation about your solution? Thanks! 
1 Like
It is not. Either try relogin or delete cache. If none of it works, use this link to submit: CodeChef: Practical coding for everyone or open from codechef ide directly.
Instead of downvoting my comment, somebody can help me out.
Hi @kamta0425,
The submit option is coming on the link : Practice
or you can directly go to this link and submit : CodeChef: Practical coding for everyone
@admin @pushkarmishra Fix the link of all solutions given in Editorial otherwise it’s of no use.
2 Likes
I see a few people shared the code for nlogn solution, but people have some unanswered questions. I had to spent a day to finally solve this beautiful problem. So I will share my approach.
PREREQUISITES :
dfs in-out time , any range update point query data structure (Segment tree with lazy propagation)
OBSERVATION:
Let’s assume we wanted to support only the queries of type U x k , and finally print the whole tree. One way to solve this problem is, to store a pair<cur_fib_term, prev_fib_term> for each node, which is initialized as {0,0} for everyone. Now for query U x k, we will update
pair(x).cur_fib + fib[k] , pair(x).prev_fib + fib[k-1].
We can observe that in the end we will just need a bfs, and while transferring the pair from parent to child, we do similar to our update operation i.e.
pair(child).cur_fib += pair(parent).cur_fib ,
pair(child).prev_fib += pair(parent).prev_fib.
Now, we want to add another parameter to our update query , depth of the node x, and we want a fresh way to combine the two update queries. If depth is same for both the update queries, that means we are updating the same subTree, so we can still continue with our previous approach of adding cur , prev fib terms of the two queries. If the depth are different, we want to make depth same.
How do we shift a
{original_cur_fib, original_prev_fib , original_depth} to {new_cur_fib , new_prev_fib, new_depth}.
Let x = original_cur_fib , y = original_prev_fib , Now let’s see how they look, as their depth start increasing
cur : x , y
After 1 : x+y, x
After 2 : 2x+y, x+y
After 3 : 3x+2y , 2x+y
After 4 : 5x+3y , 3x+2y
So, after going d steps down, the same pair will look like
{ fib[d+1]*x + fib[d]*y, fib[d]*x + fib[d-1]*y }
Just how we went increasing depth, one can draw the other version of decreasing depth and find a similar kind of pattern .
So, now we know, how to make depth of two equal, and hence we know how to combine.
So if we can keep a triplet {x,y,d} for each node of the tree, in the end, we query the current node, and shift the result to the depth we need , and print the result.
Implementation