Kirchoff's tree theorem was recently used in https://atcoder.jp/contests/abc253/tasks/abc253_h, and it on first glance, almost feels like black magic, but I will show that it is not the case.

So prerequisites... Advanced contestants may skip these

Arborescences and functional graphs

An arborescence rooted at $$$r$$$ is a tree directed in such a way, such that every node is reachable from $$$r$$$. A functional graph induced by $$$f$$$ on $$$V$$$ is a graph such that the set of directed edges is $$$(x, f(x))$$$ for each $$$x \in V$$$ where $$$f(x)$$$ is defined. An arborescence is the transpose(graph with all edges reversed) of a functional graph with $$$f : [1, r-1] \cup [r+1, n] \to [1, n]$$$. Every functional graph may not form an arborescence, they may have cycles. Notice any cycle must be a directed cycle, as every node has exactly one out edge.

Modeling counting spanning arborescences as counting acyclic functional graphs

Let $$$G$$$ be an undirected graph. We would like to count the number of arborescences rooted at $$$r$$$ in $$$G$$$. Let us root the arborescence at $$$1$$$ for convenience without loss of generality. Let's look at all functions $$$f : [2, n] \to [1, n]$$$ where $$$f(x) \in G_x$$$, where $$$G_x$$$ is the set of nodes connected to $$$x$$$ by an edge. Note any arborescence in $$$G$$$ must correspond to some $$$f$$$ satisfying these constraints, and every arborescence that has an edge not in $$$G$$$ cannot satisfy the given constraints. So we can model the problem as counting the number of functional graphs induced by $$$f$$$ without cycles. Let the set of valid functions be $$$F$$$.

Counting acyclic functional graphs with $$$PIE$$$

Let $$$C_F$$$ be the set of possible cycles in functional graphs induced by functions $$$f \in F$$$. Let $$$c \subseteq C_F$$$ be some subset of cycles in $$$C_F$$$. Let $$$F(c)$$$ be the number of functions in $$$f$$$ with the cycles in $$$c$$$. Then the number of acyclic functional graphs in $$$F$$$ is

Computing $$$F(c)$$$

Notice, that the set $$$c$$$ must consist of only disjoint cycles. Then $$$F(c) = \prod |G_x| = \prod deg_x$$$ for all $$$x \in V$$$ that is not contained in any cycle in $$$c$$$, since $$$f$$$ is already fixed for the elements in the cycles, and the ones not in any cycle could be anything.

How to use determinants to compute this

Since $$$c$$$ is a set of disjoint cycles, and so is a permutation, we can try counting over all permutations. Let us consider some set of cycles $$$c \subseteq C_F$$$. If $$$c$$$ is not disjoint, we can ignore it. Otherwise, let there be a permutation $$$P$$$ of $$$[2, n]$$$ with the set of disjoint cycles in $$$c$$$, and for those not in $$$c$$$, we can have a self loop. This permutation should be weighted by $$$(-1)^{|c|} \prod_{P[x] = x} deg_x = \text{sgn}(P)\prod_{P[x] = x} -deg_x$$$. Notice this is true, because $$$|c|$$$ is the number of cycles in $$$P$$$ of size more than $$$1$$$, and then we multiply over all elements in cycle of size $$$1$$$.

Notice that the set of cycles in $$$P$$$ are only valid if there exists edge $$$(i, P_i)$$$ for each $$$i$$$ with $$$i \not= P_i$$$. Then we should make matrix $$$M$$$ with $$$M_{i, P[i]} = 1$$$ if there exists such edge and $$$M_{i, P[i]} = 0$$$ otherwise. Any permutation with a cycle not in $$$C_F$$$ will contribute $$$0$$$ to the determinant. We let $$$M_{i, i} = -|G_i| = -deg_i$$$, so that the permutation is weighted by the product of $$$-deg_x$$$ over all self loops. We should remove the row/column corresponding to $$$1$$$, as there is no edge from $$$1$$$, and no cycle in $$$C_F$$$ containing it either. Then it's not hard to see that the determinant here computes the above sum. As an exercise you can show that you can find number of arborescences rooted at $$$r$$$ for each $$$r$$$ in a directed graph using a similar method.