What bounds can be put on counting reachable nodes in a dag? Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is there reason to believe the lower bound can be improved (related: what exactly is known about lower bounds for transitive closure)?

Motivation: I had to do this a couple of times while representing fol formulas as dags.

Edit: Please note that simply doing $c_x=1+\sum_{x\to y}c_y$ counts paths, not reachable nodes. (I added this because apparently many people thought this simple solution would work by the votes I saw on a now-deleted answer.) In fact, this problem appears precisely when you want to do something interesting with 'shared' parts, nodes reachable by more than one path. Also, I say dag, because if they are solved, then solving digraphs is easy.
The transitive closure of a directed graph with $m$ edges and $n$ vertices can be computed 
slightly faster than $O(mn)$ time, but not by much. An $O(n^2 + mn/\log n)$ time algorithm is mentioned in a footnote of Chan's 2005 WADS paper on APSP (journal version in Algorithmica 2008). A slight improvement to $O(n^2 + mn \log(n^2/m)/\log^2 n)$ can be found in the ICALP'08 paper "A New Combinatorial Approach for Sparse Graph Problems " by Blelloch, Vassilevska and Williams.
That being said, I don't know whether counting descendents is easier than actually finding them