"But I have one more thing to talk about...".
The Rundown
This problem can be solved in O(N lg N) time, but requires us to
think about the graph completely differently. Google could not
help me here. This method took several rewrites, along with
drawings, and spreadsheets to figure out a mathematical approach to
skip
all steps and generate the correct answer...
instantly.
The result? There is a way to find out the number of combinations
for everything in
constant time with the use of a
magic
number that we compute before traversing the tree. In fact,
computing this number takes up the most time in this method.
I make some observations in my slides:

"There are N children in each node, but only 1 parent."
Whenever considering how to traverse the graph, the most
common way would be using a topdown approach. However,
in this case, that'd mean we would have to go through N
children for each node. Why do that when we could just go
up? Since there's only one parent, it reduces N to 1.

"Don't traverse nodes. Multiply combinations instead."
When checking for arms, legs, and lower body nodes, we
don't have to resort to traversal. With a magic number,
we can simply compute the number of combinations
instantly.

"Number of head combinations is equal to depth."
Store the depth of each node in the graph/tree.
If we do a bottomup approach pivoting on upper body
nodes, we can compute the number of possible head
configurations by simply looking at its depth (since
all nodes above a man can be considered an extra head
configuration).

"Store a magic number (N_{p}) that we can
subtract probabilities from."
I'm getting there... If we know a child's number of
combinations (excluding the parent), it is possible to
figure out the number of combinations for the current
node. It is also possible to compute the number of
combinations of a node subtracted by another
node's magic number. Since we are going with a bottomup
method, every node is guaranteed to have a valid magic
number.
Generating N_{p}, the Magic Number
In the slides, I define N
_{p} as follows:
Of course, no one understood what this actually meant. So I'll go
over it. Let's use slide 30 as a reference point:
Each node will have its very own N
_{p} value, as well as
its very own C value. In this context:
 N_{p}  Magic Number
 C  Number of possible nodes it can go to (including itself, but not parents)
Let's look at Node 1. That N
_{p} is 23! Where did that come
from? Let's look at what Node 1 can go to...
 Node 2  with a C of 1 (as it can go to only itself)
 Node 3  with a C of 3 (as it can go to 3, 4, 5)
 Node 6  with a C of 5 (as it can go to 6, 7, 8, 9, 10)
We have all we need to compute
N_{p} now. Rather
than give a mathy definition, I'll give pseudocode.
Pseudocode
Set N_{p} to 0.
Set INC to the C of the first child.
For every child (starting from the second one) {
N_{p} += (INC * current child's C)
INC += current child's C
}
Working it out by hand,

Set INC to the first child's C. This is 1.

Loop from the second child on...

Second Child (Node 3)...

N_{p} is incremented by second child's C
multiplied by INC. N_{p} += 1 × 3. This gives
us an N_{p} of 3.

INC is incremented by the child's C. INC += 3.
This gives us an INC of 4.

Third Child (Node 6)...

N_{p} is incremented by third child's C
multiplied by INC. N_{p} += 5 × 4. This gives
us an N_{p} of 23.

INC is incremented by the child's C. INC += 5.
This gives us an INC of 9.

Return N_{p}, which is 23.
Do this for every node in the graph. We can avoid making it O(N
^{2}) by
being clever. Have each node build this value up incrementally as others are
added into the graph (loop upwards to the root). This gives it an O(N lg N) time.
"Okay Clara that's nice and all, but what can I do with N_{p}?"
N
_{p} allows us to compute the number of combinations for all arms
instantly
if we have an upper and lower body node defined. This is defined by the following
equation:
From slide 32...
If we assume that the upper body node is Node 1 and assume that the lower body
node is Node 6, we can compute all possible combinations of arms with the
given equation.
We know that Node 1's N
_{p} is 23. We also know that Node 1's C is 10, and
Node 6's C is 5. Therefore:
We can even check our answer. Possible arm combinations include 23, 24, 25.
We didn't have to traverse at all. That entire step was skipped.
So what's next? We can multiply out the combinations of legs, arms, and the
depth of the head node to generate the number of possible men from an
upper/lower body pair in constant time.
Comparing to Dynamic Programming w/ Memoisation
Dynamic Programming
never had a chance...
The problem limit was 2,000 nodes. This implementation solves a
graph of 50,000 nodes
in under 10 milliseconds. I think
that's overkill enough for this talk.