Hackerrank - Recurrent on a tree

general
1

I can’t understand the editorial, please help. Link: problem

1 Like
2

Actually you can solve this question by dp on trees…

For a while ,think that the problem is to find sum of all the numbers that lie on the path from every ‘u’ to every other ‘v’.(this is similar to original problem except that in this case you have to find sum of numbers instead of fibonacci(sum of those number) )…

Here Fibonacci(k)=kth fibonacci number…

Now suppose that you are on a particular node in a tree and you have to find something related to every possible path in the subtree of current node…

There are two possible case

  1. Whole path lie inside subtree without passing through current node(these answers you have already updated in some global variable in which final answer is to be stored)

  2. It passes through current node(now we will do some calculations and update the answer)…

Now for calculating the second part is standard dp…

suppose that for every child node you already have a sum stored in it (sum of paths starting from that child node and going till the leaf node)…

so to update the answer for current node you would concatenate the current node to all the paths that start from its child node ,so that it contains all the new paths that start from this node and go till leaf node.
but there are also some paths that go from its one child child to another and passing through current node.
for these paths you have to merge the answer from all the child (you can figure this out by doing some example on pen and paper…)

Now coming back to original question,we know that fibonacci(a+b)=(M^a)*(M^b)=M^(a+b)…
(here M is the fibonacci matrix described in editorial).
so in this question think instead of sum you have stored a list of matrices like (M^a)+(M^b)+(M^c) etc…

here a,b,c are actually the sum of paths starting from a particular child and by raising matrix M to its power a we can be able to find ath fibonacci number easily…
now if current node stores a number ‘k’ then you can easily concatenate it with all the paths starting from its child by multiplying matrix M^k to matrix stored in child node…

example
[(M^a)+(M^b)+(M^c)]*[M^k]=[M^(a+k)]+[M^(b+k)]+[M^(c+k)]…

this is nothing but sum of all fibonacci numbers of paths that starts from current node and go till leaf node…
and similar calculation can be done while merging answer from its child nodes…
you can do this by performing a dfs and building the answer till the root node and keep on updating the final answer at each step…

hope it helps…