Efficiently listing all last-level descendants of each root in a proper hierarchical graph (bipartite DAG)
Define $\ell(v)$ to be the leaves reachable from a node $v$. Note the following:


  Lemma 1: For all non-leaf nodes $v$ we have: $$\ell(v) = \cup_{u \in c(v)} \ell(u)$$ where $c(v)$ is the set of all children of $v$.


We now construct an algorithm around this:


Let $A = \{v_1, v_2, \ldots, v_n\}$ be the reverse topological order of nodes in $G$.
For all $v \in A$:


If $v$ is a leaf node, define $\ell(v) = \{v\}$.
Otherwise, define $\ell(v)$ as we did in Lemma 1.



Now the complexity of this is $O(km + n)$ where $k$ is the average cost of union-ing the $\ell$-sets of the children of a non-leaf node. How you go about union-ing the sets is up to you. Standard merging is easy to implement. You could also try using a disjoint-set data structure, but this becomes tricky because a node might have multiple parents.