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

Problem statement

Given an undirected graph $$$G = (V, E)$$$ with no multi edges or self loops, find the number of spanning trees in $$$G$$$.

Bijection between spanning trees and Arborescences

Let us consider all arborescences of $$$G$$$ rooted at $$$r$$$. We can undirect the arborescence to get a spanning tree of $$$G$$$. We can direct all edges of $$$G$$$ away from $$$r$$$ to get the arborescence back. Therefore they are equal in number.

Representing an arborescence as a functional graph transpose

An arborescence is the transpose of a functional graph with $$$f : [1, r-1] \cup [r+1, n] \to [1, n]$$$, where $$$f$$$ corresponds to the parent function in the arborescence. 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 in 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$$$ that do not contain $$$1$$$. 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

Notice this is true, because $$$|c|$$$ is the number of cycles in $$$P$$$ of size more than $$$1$$$, and then we multiply $$$-1$$$ 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. We should multiply by $$$(-1)^{n-1}$$$ or take the absolute value of the determinant. Alternatively, you can multiply each entry by $$$-1$$$ and get $$$M_{ij} = -1$$$ and $$$M_{u, u} = deg_u$$$, and then just take the determinant. As an exercise you can show that you can find number of arborescence rooted at $$$r$$$ for each $$$r$$$ in a directed graph using a similar method.

Spanning arborescence of directed graphs

If you have understood upto here, You should notice that $$$deg_i$$$ should really be indegree and whether you mark directed edges $$$(u, v)$$$ at $$$M_{u, v}$$$ or $$$M_{v, u}$$$ doesn't really matter.

Expected spanning trees

Let's assume you're given some set of edges, and each edge has some probability of being in our graph. We can compute the expected number of spanning trees. Notice that the old matrix is just sum of product of all edges over all spanning trees. Every spanning tree has a weight of 1 when all edge weights are 1. But if we weight every spanning tree by the product of the probability of each edge, we will get the probability of this spanning tree in our graph. Then summing this over all spanning trees gives us the expected number of spanning trees. For every edge $$$(u, v, p)$$$ you should set $$$M_{v, u} = M_{u, v} = p$$$, and $$$deg_u$$$ should be $$$sum(M_{u})$$$.

Counting spanning forests with mutliple roots.

Let $$$R$$$ be the set of roots. You can remove the row and column corresponding to every node in $$$R$$$. This essentially tells the matrix to not count parent pointers for any node in $$$R$$$, as required.

Counting minimum spanning trees

Iterate over edge weights in increasing order. The edges of the current edge weight, form some connected components. You should multiply the answer by the number of spanning trees of each component. Then merge each connected component into one node, and then repeat for the next smallest edge weight. This will amortize into $$$O(V^3)$$$ since the total component size of components with more than one node is less than $$$2V$$$.