Number of descendants of each node in a DAG
Topologically sort the nodes in your DAG.
For each node N, set N.QueryCount = 0.
For each node N, in reverse topological order:

Set N.Descendants = {N} U {C.Descendants | C in N.Children}.
Yield (N, N.Descendants.Count) from the algorithm.
If N.Parents is empty, you can dispose of N.Descendants.
For each C in N.Children, increment C.QueryCount. If C.QueryCount == C.Parents.Count, you can dispose of C.Descendants.



This of course is expensive if your node degrees are large. Worst case complexity may not be significantly better than your unspecified "naive algorithm."

The issue is that this is a very difficult problem to solve.  Suppose there is a DAG with millions of nodes, millions of edges, etc. I show you this portion of the graph:

A--&gt; B
 \-&gt; C


How many descendants does A have?  The number of descendants of B plus the number of descendants of C minus the number of common descendants of B and C.  It's the third term that creates the difficulty.  You can't know just the number of descendants of B and C - you need to also know what the descendants are.