I just solved the problem Facebook Hacker Cup 2015 — Round 1 — D. Corporate Gifting
My solution used "dp on tree" technique. The naive version would have used entire arrays in nodes that represents a discrete functions with its values. Because for every function all the function values are the same except one value, I can represent it with the common value, index of the difference, and the difference itself. Using this simpler representation the calculation of the sum of the functions will have lower complexity.
I wonder if this technique (of representing discrete functions this way) has some other useful applications. Is there any reading about this topic?