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. the problem can be summarized as the following: .

thus, we can run this dp for each component and sum up to find the final answer.

I am sure there are easier ways to set up the dp but that is the way which I found most intuitive so yeah