hello. I have noticed after solving a few problems that there is no documentation on this topic, thus, I have decided to write a short blog on this topic.

note that this is simply an extension of dp on a tree, so it is strongly recommended you study dp on a tree before reading this blog.

firstly, a functional graph is defined as a graph where each vertices has exactly one out degree. a key feature of these graphs is that a connected functional graph, there is always one and only one cycle present. a proof is attached here. this is crucial to our dp.

consider the following problem