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:

Given $$$N$$$ people, person $$$i, 1 \leq i \leq n$$$ can donate $$$a_i$$$ but will not donate if there is a person $$$b_i$$$ which donates. Find the most amount of money that can be donated.

we can model the problem as directed edges from a person to the person they hate, making this will lead to a functional graph. notice that their may be multiple connected components, each component a n individual connected functional graph. thus, we should find the optimal amount for each component and add them up to find the final answer. but there is a problem: we cannot directly run the dp on each component since there is a cycle.

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