Find all the cumulative sums in a DAG
It's possible to do slightly faster, by using sophisticated algorithms for transitive closure based on fast matrix multiplication, but apparently it is not known how to do this much faster than the naive solution.  See https://cstheory.stackexchange.com/q/553/5038 and https://cstheory.stackexchange.com/q/736/5038 and https://cstheory.stackexchange.com/q/4258/5038.