Find all the cumulative sums in a DAG Let's call G a DAG (directed acyclic graph) with N nodes labeled with a natural value.

We define the cumulative sum of a node v as the sum of the value of all the ancestor nodes of v (including v).

For example, the cumulative sum of d in the following DAG is 7:

      a (2)
     / \
    v   v
(1) b   c (3)
     \ /
      v
      d (1)


Is it posible to compute the cumulative sum for a set of M nodes in G, in less than O(M*(N + E))?



Clarification: computing the cumulative sum for a set of nodes refers to computing the cumulative sum for each node of the set.



Further clarification: for a given cumulative sum, each ancestor is counted only once (notice that the ancestors of $u$ include $u$):

$cumsum(v) = \sum_{u \in \text{ancestors of } v} \text{value of } u$

Which does not imply:

$cumsum(v) = \text{value of } v + \sum_{u \in \text{direct ancestors of } v} cumsum(u)$

because this last formula may count ancestors multiple times. For example, in the diamond example we have:  

$cumsum(d) = 7$
$cumsum(b) = 3$
$cumsum(c) = 5$
so $cumsum(d) \neq 1 + cumsum(b) + cumsum(c)$



Solution in O(M*(N + E)):


  To compute the cumulative sum of a single node v in O(N + E), sort the
  DAG topologically and traverse the sorted list of vertices backwards,
  tainting all ancestors of v with the back edges, and adding the values
  of all the ancestors. (You could also just do a DFS for the same
  price).
  
  Doing this for each node in the given set of M nodes gives a running
  time of O(M*(N + E)).
  
  Although it doesn't affect the final running time, the topological
  sort could be done only once before looping through each cumulative
  sum calculation.
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.