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. this is my first educational blog so please excuse me if there are errors.

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 in 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 using directed edges from a person to the person they hate, making this a functional graph. notice that their may be multiple connected components, each component an 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 will use

note that there is also an edge case where the cycle in the connected component is of length $$$2$$$. in this case, we will obviously not delete the edge as the cycle itself is an edge.

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.

thank you for reading :)