lgv引理矩阵树

1。哭哭，不是很会线代。。。

真的瞎说属于是了。。

lgv

lgv讲的是你有一个dag（有权），并且钦定了 \(n\) 个源，\(n\) 个汇。

路径权值定义成了边权的乘积。

你要先匹配路径端点，也就是对于 \((i,p_i)\) 含义就是 \(i\) 号源，匹配到 \(p_i%\) 号汇。

你要计算的是 ，对于每一种匹配方式，大小为 \(|n|\) 的路径的集合，使得集合中路径两两无交，并且都是 \(i\) 源到 \(p_i\) 汇的路径 的 权 乘积的有符号和。

有符号和就是每个排列要算上 \(\tau(p)\)。 \[ \begin{aligned} \mathrm{ans}=\mathrm{det(M)}\\ M_{i,j}=E(i,j) \end{aligned} \] \(E(i,j)\) 含义是从 \(i\) 源到 \(j\) 汇所有可行路径权值的和。

为什么呢？你看一下行列式本质上也是在枚举 \((i,p_i)\) 只不过，他把所有可行的路径权都乘起来了。

由于是带符号和，对于一个交集不为空的路径集合 \(\mathcal{P}\) 考虑源最小的，第一次相交的位置，比如说。

\((a,p_a),(b,p_b)\) 第一次交于 \(x\)。

\((a,x,p_a),(b,x,p_b)\) 我们把它映射到 \((a,x,p_b) , (b,x,p_a)\) 就是把路径翻折，想卡特兰那样，是可以构成双射的。

比较显然。因为钦定了最小的，不难发现由于 \(p_a,p_b\) swap 了，所以逆序对奇偶改变，所以抵消。

---

矩阵树

无向图

矩阵树不会证明、。。

无向图就是说生成树个数为 \((D-E)\) 的余子式 (degree-edge) ，带权的生成树和可以看成重边。

实际上我们应该忽略自环。

注意无向图对于一条边 \((x,y)\) 会给 \(E_{x,y},E_{y,x}\) 两个贡献。

---

有向图

有向图情况就分为两种情况了。

根向生成树，边指向定好的根,答案为 \((D^{out}-E)\) 去除根的那一行那一列的余子式。

叶向生成树，边来自定好的根,答案为 \((D^{in}-E)\) 去除根的那一行那一列的余子式。

记忆方法，可以画一个2个点一条边的图看答案。

\(E\) 是有向图，所以 \((x,y)\) 只会提供 \(E_{x,y}\) 的贡献了。。。

---

best 引理

一个欧拉图（有向）\(x\) 开始的欧拉回路 个数为：

\(C\cdot\mathrm{deg}_x\prod (\mathrm{deg}_u-1)!\)

\(C\) 是 \(x\) 为根的根/叶向树。

大概是构造了这样一个双射，一个根向树对应着 若干 欧拉回路。

我们把非树边随意排序，然后我们通过一个树+排列构造一个欧拉回路。

我们按定好的序走非树边，最后走那条树边。由于你求欧拉回路的时候就能保证一定存在，所以这么做一定构造出欧拉回路。

那么如何说明一个欧拉回路一定对应这一个树+序列？

每个点最后一次到的时候连边。只需要说出没有环即可。

如果有环说明终点在环上，但是很遗憾终点是根，并且根不能有出边。。。。双设成立。

回忆一下有向图有欧拉回路充要条件是每个点 入度=初度。

有欧拉路的充要条件是 只存在两个点不满足上述条件，一个入-出=1，另一个是-1。

那么我们不难想到欧拉路个数实际上只需要连一条，并且钦定是树边即可。