终于学到这个了，本来准备省选前学来着的？
前置知识：矩阵行列式
矩阵树定理
矩阵树定理说的大概就是这样一件事：对于一张无向图 \(G\)，我们记 \(D\) 为其度数矩阵，满足 \(D_{i,i}=\text{点}i\text{的度数}\)，\(D_{i,j}=0(i\ne j)\)，再记 \(A\) 为其邻接矩阵，满足 \(A_{i,j}=i,j\text{之间边的条数}\)，如果有重边则算作多条边。
设 \(K=D-A\)，那么去掉 \(K\) 第 \(k\) 行第 \(k\) 列（\(k\) 任意）得到的矩阵 \(k'\) 的行列式就是 \(G\) 中生成树的个数。
这样的矩阵 \(K\) 又被称为 \(G\) 的基尔霍夫矩阵，注意到这里的 \(k\) 可以取任意值，也就是说去掉任意第 \(k\) 行第 \(k\) 列后得到矩阵的行列式都是相同的（\(n-1\) 阶主子式）
证明鸽掉了，因为 cmd_blk 也不会，所以就只能靠记忆力咯
矩阵树定理可以扩展到带权值的情况，即求图 \(G\) 所有生成树权值之积的和，但是这样度数矩阵和临界矩阵的定义就要发生变化了，重新定义度数矩阵为 \(D_{i,i}=\text{所有与}i\text{相连的边的权值之和},D_{i,j}=0(i\ne j)\)， 邻接矩阵 \(A_{i,j}=i,j\text{之间边的权值之和}\)，剩余部分都和不带权的情况相同了。
矩阵树定理也可以扩展到有向图的情况，不过有向图的生成树就要与无向图加以区分了，有向图的生成树可以分为两种，叶向树和根向树，两类生成树都要指定一个根节点 \(r\)，其中叶向树满足从根开始 DFS 整棵树，经过的所有边都指向其儿子；根向树满足从根开始 DFS 整棵树，经过的所有边都指向其父亲。
那么以某个点 \(r\) 为根的叶向树和根向树的个数怎么求呢？我们记 \(D^{\text{in}}\) 为入度矩阵，\(D^{\text{in}}_{i,i}=i\text{的入度},D^{\text{in}}_{i,j}=0(i\ne j)\)，类似地定义了 \(D^{\text{out}}\)。记 \(A_{i,j}=i,j\text{之间边的条数}\)，再记 \(K^{\text{in}}=D^{\text{in}}-A\)，\(K^{\text{out}}=D^{\text{out}}-A\)，那么：
- 以 \(r\) 为根的根向树个数即为 \(K^{\text{in}}\) 去掉第 \(r\) 行第 \(r\) 列后的行列式
- 以 \(r\) 为根的叶向树个数即为 \(K^{\text{out}}\) 去掉第 \(r\) 行第 \(r\) 列后的行列式
如果实在记不清叶向树对应 \(K^{\text{in}}\) 还是 \(K^{\text{out}}\) 可以这么理解：叶向树，顾名思义，是从根节点指向叶节点，可以看作一个发散的过程，所以应该是“out”，根向树也就是“in”了。
BEST 定理
BEST 定理说的是这样一件事：对于一个欧拉图（有向图）而言，其以 \(x\) 出发，\(x\) 结束的欧拉回路的个数为 \(C\times deg_x\prod\limits_{u\in V}(deg_u-1)!\)，其中 \(C\) 为以 \(x\) 为根的根向树（叶向树也没问题，因为反正是欧拉图，每个点入度等于出度）的个数。
为什么呢？首先我们考虑图的任意一棵根向树，对于再每个节点我们将以 \(u\) 为起点的所有不在根向树上的 \(deg_u-1\) 条出边（当然如果 \(u\) 为根节点就有 \(deg_u\) 条不在根向树上的出边）钦定一个顺序，方便起见我们称这个根向树及这个出边的排列顺序为一个“组合”，显然证明原命题我们只需证明一下两个部分：
- 每个组合唯一对应一条欧拉回路
- 每条欧拉回路唯一对应一个组合
先考虑第一个命题，我们考虑这样一个走法：从根节点开始，每到达一个节点，如果除了该节点与其在根向树上与父亲相连的边，其余边都被走过了，那么就沿着根向树上的边走向其父亲，否则就按照钦定的顺序走向下一条边。
显然这样每条边最多被访问一次，不过为什么这样走总可以得到一个欧拉回路呢？会不会走到一个地方走不下去了呢？
考虑反证法，假设走到某个点 \(u\) 之后走不下去了，如果 \(u\) 不是根节点，那么显然我们每次经过 \(u\) 都会经过它的一条入边和一条出边，而这次访问 \(u\) 只访问了 \(u\) 的一条入边，也就是说 \(u\) 的入边个数等于出边个数 \(+1\)，与原图为欧拉图矛盾。如果 \(u\) 是根节点并且到达 \(u\) 的时候没有访问完全部边，那么必然 \(\exists\) 某条根向树上的边 \(e=(x,fa[x])\) 没有被访问，这样一来 \((fa[x],fa[fa[x]]),(fa[fa[x]],fa[fa[fa[x]]]),\cdots\) 也都不会被访问，也就是说根节点存在一条入边被访问，根据原图为欧拉图知 \(u\) 必然有一条出边没有被访问，矛盾！
因此每个组合唯一对应一条欧拉回路。
再考虑第二个命题，我们记 \(e_u\) 为 \(u\) 最后访问的入边，下证所有 \(e_u\) 构成一棵根向树，还是采用反证法，如果有环，那么根节点必然不会在环上，而由于换上的某个点 \(x\) 走一圈之后还能回到 \(x\)，根据原图是欧拉图，\(x\) 的入度等于出度，即访问完 \(e_x\) 后 \(x\) 经过的入边条数等于出边条数，而绕一圈又回到了 \(x\)，又对 \(x\) 经过的入边条数产生 \(1\) 的贡献，故 \(x\) 的入度等于出度 \(+1\)，矛盾！
故原命题成立。
关于欧拉回路计数还有一个注意点，就是如果题目要求“经过所有边恰好一次”，那么孤立点是需要排除在外的，注意特判这一点。