DDOSvoid's Blog

矩阵树定理

发表于 更新于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

简介

大概就是用来求 $\sum_{T \in Tree}\prod_{e\in T}w_e$ 的值

需要注意矩阵树定理是默认不存在自环的，但实际是否存在自环不会影响基尔霍夫矩阵的构造

构造

基尔霍夫矩阵：

无向图

有向图，对于外向树和内向树 $i\neq j$ 时都相同，$i=j$ 时，内向树我们只考虑 $i$ 连出去的边（出度），反之外向树我们只考虑连向 $i$ 的边（入度），下面以外向树为例

我们删掉第 $k$ 行第 $k$ 列后求矩阵行列式得到的即为以 $k$ 为根的 $\sum_{T \in Tree}\prod_{e\in T}w_e$，虽然无向图中这并没有区别

技巧

求 $\sum_{T \in Tree}\sum_{e\in T}w_e$

我们把每条边的贡献写成 $w_ex+1$，将其看成多项式，最后答案就是行列式的一次项的系数，所以乘法变成了模 $x^2$ 的多项式乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct node {
    int x, y;

    node (int x = 0, int y = 0) : x(x), y(y) {}

    friend node operator + (const node &u, const node &v) {
        return node(add(u.x, v.x), add(u.y, v.y));
    }
    friend node operator - (const node &u, const node &v) {
        return node(add(u.x, p - v.x), add(u.y, p - v.y));
    }
    friend node operator * (const node &u, const node &v) {
        return node(add(mul(u.x, v.y), mul(u.y, v.x)), mul(u.y, v.y));
    }
    friend node operator / (const node &u, const node &v) {
        ll inv = pow_mod(v.y, p - 2);
        return node(add(mul(u.x, v.y), p - mul(u.y, v.x)) * inv % p * inv % p,
                    mul(u.y, inv));
    }
};

node g[maxn][maxn];
int Gauss(int n) {
    node res(0, 1);
    for (int i = 1; i <= n; ++i) {
        int pos = -1;
        for (int j = i; j <= n; ++j) if (g[j][i].y) pos = j;
        if (pos == -1) return 0; swap(g[i], g[pos]);
        if (pos != i) res = res * node(0, p - 1);
        res = res * g[i][i]; node inv = node(0, 1) / g[i][i];
        for (int j = i + 1; j <= n; ++j) {
            node div = g[j][i] * inv;
            for (int k = n; k >= i; --k) g[j][k] = g[j][k] - div * g[i][k];
        }
    } return res.x;
}

例题

  1. 简要题意：给定一个完全图，每条边的权值表示这条边存在的概率，求存在的边恰好构成一棵生成树的概率

    $n\le 50$

    简要题解：首先容易得到答案为 $\sum_{T\in Tree}(\prod_{w\in T}p_e\prod_{w\notin T}(1-p_e))=\prod 1-p_e\sum_{T\in Tree}\sum_{e\in T}\frac{p_e}{1-p_e}$

    后面那个东西用矩阵树定理来求就行了，需要注意如果 $|1-p_e|<\epsilon$，为了精度，我们需要将 $p_e$ 减掉 $\epsilon$

    Luogu P3317 [SDOI2014]重建

  2. 简要题意：现在有 $n$ 个城市，有 $n-1$ 个公司来修路，每个公司可以修某些路，现在要求恰好修 $n-1$ 条路使这 $n$ 个城市连通并且每个公司恰好其中一条路的方案数

    $n\le 17$

    简要题解：我们考虑枚举这次负责修路的公司 $S$，然后用矩阵树定理算出总的方案数 $f_{S}$，令 $g_{S}$ 表示 $S$ 中的每个公司都至少修了一条路的方案数，容易得到 $f_{S}=\sum_{T\subseteq S} g_T$，根据子集反演，可以得到 $g_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}$

    因为恰好有 $n-1$ 个公司，所以答案就是 $g_U$，$U$ 表示这 $n-1$ 个公司的集合，时间复杂度 $O(2^nn^3)$

    Luogu P4336 [SHOI2016]黑暗前的幻想乡

  3. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，定义一个生成树 $T$ 的价值为 $\sum_{i=1}^{n-1}w_{e_i}\times(w_{e_1},w_{e_2},\cdots,w_{e_{n-1}})$ ，求所有生成树的价值之和

    $n\le 30,m\le \frac{n(n-1)}{2}w_i\le 152501$

    简要题解：首先考虑将 $gcd$ 拆掉，然后对式子进行化简

    矩阵树定理将 $\prod$ 转换成 $\sum$ 是经典 $trick$，但现在的问题是如果枚举 $d$，那么时间复杂度 $O(n^3w_i)$，无法通过此题

    这个时候我们考虑只有枚举 $d$ 之后边数大于等于 $n-1$ 才跑矩阵树定理，那么这样的时间复杂度为 $O(\frac{\sum_{i}\tau(i)}{n-1}n^3)$，但是注意到边只有 $n^2$ 个，所以实际上的复杂度应该为 $O(\frac{n^2\times 144}{n-1}n^3)$，$144$ 是一条边的约数最大值，而且实际上也跑不满

    Luogu P6624 [省选联考 2020 A 卷] 作业题

  4. 简要题意：给定一个 $n$ 个点无向树，求对于 $k\in[1,n - 1]$，有多少棵这 $n$ 个点的完全无向图的生成树与这棵树有恰好 $k$ 条边重复

    $n\le 100$

    简要题解：我们考虑令树边的权值为 $x$，非树边的权值为 $1$，那么对这张图用矩阵树定理求求出的 $n-1$ 次多项式的系数就是我们要的答案，但我们显然不能直接暴力拿多项式来做矩阵树定理，我们考虑带 $n$ 个值进去，然后再用拉格朗日插值插出我们要的多项式即可，时间复杂度 $O(n^4)$

    CF 917D Stranger Trees

  5. 简要题意：给定一个 $n$ 个点的带权完全无向图，给定 $k$，求所有生成树的权值的 $k$ 次方之和

    $n,k\le 30$

    简要题解：我们知道 $(\sum_{i=1}^{n-1}w_i)^k=\sum_{i\in[1,n-1],a_i\ge0,\sum_{a_i}=k}\binom{k}{a_1,\cdots,a_k}\prod_{i=1}^{n-1}w_i^{a_i}$，这是一个多项式卷积的形式，我们考虑将其看做生成函数，相当于 $ans=k![x^k]\prod_{i=1}^{n-1}e^{w_ix}$

    我们把每条边看做一个 $k$ 次的多项式，然后做矩阵树定理即可，因为 $k$ 很小，所以求逆和乘法直接 $O(k^2)$ 暴力即可

    时间复杂度 $O(n^3k^2)$

    Luogu P5296 [北京省选集训2019]生成树计数

  6. 简要题意：给定一个 $n$ 个点 $m$ 条边的有向图，求以每个点为根的外向树的个数

    $n\le 500$

    简要题解：我们令 $A$ 表示该图的基尔霍夫矩阵，不妨设 $r(A)=n-1$，如果 $r(A)\neq n-1$，那么答案肯定都是 $0$

    为 $n-1$ 的 $n$ 阶方阵 $A$ 的伴随矩阵 $A^$ 的秩为 $1$，因为 $A$ 的秩为 $n-1$，所以一定存在不全为 $0$ 的实数 $x_1,\cdots,x_n$ 使得 $\sum_{i=1}^nx_ia_i=0$，其中 $a_i$ 表示 $A$ 的第 $i$ 行的行向量，同理可以得出关于列向量的 $y_i$，可以证明 $A^$ 的第 $i$ 行和第 $j$ 行的比例为 $\frac{x_i}{x_j}$，列同理，那么有 $A_{a,b}=A_{i,j}\frac{x_ay_b}{x_iy_j}$

    对于一组 $x,y$，我们只需要高消一下即可，然后找一个不为 $0$ 的 $x_i$ 和 $y_j$ 然后求出 $A_{i,j}$ 即可求出所有的 $A_{k,k}$

    时间复杂度 $O(n^3)$

    2022杭电多校10 J Tree