By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll also only consider DAGs for obvious reasons.
Imaginably, this is a hard query to google for. I'm looking for a complexity that is more precise than just "exponential" - is there some nice property of a graph that expresses this? For example, it would be convenient if the complexity would be linear if we the graph is just a tree. Maybe treewidth is helpful?