纯纯的随笔

1. 有向图欧拉回路计数：

欧拉回路与一颗 \(1\) 为根且非树边排列好的内向树形成双射。

欧拉回路映射内向树：把最后一条边看做树边，剩下走过的看做非树边。

内向树映射欧拉回路：能按顺序走非树边就先走非树边，最后走树边。

于是答案是 \(T_1d_1!\prod_{i=2}^n(d_i-1)!\)，其中 \(T_1\) 是以 \(1\) 为根的内向树数量，可以矩阵树定理求出。

不要求终点也可以钦定 \(1\) 是终点，非树边中 \(1\) 的第一条边是访问边，答案是 \(T_1\prod_{i=1}^n(d_i-1)!\)。