生成树

承接上篇。

无向图最小生成树

简单题目

并非简单。

P1967

考虑求出最大生成树后倍增 LCA 处理树上两点间的最短路径，答案就是这个。

CF888G

类似 Kruskal，我们考虑找尽可能短的边权连接两个连通块。

考虑建一棵 trie 树，从高位到低位加入所有数。对于一个点 \(p\) 的左右子树中存的 \(a\)，若左右子树内部分别连通，则我们一定要连一条边将左右子树合并起来。原因是如果与 \(p\) 外的状态连边，则代价一定更高。

所以考虑枚举左子树中的值，在右子树中找最小值连边。每个数最多考虑 \(\log V\) 次，所以复杂度是 \(O(n\log^2 V)\)。

CF1305G

先建立一个虚点 \(a_0 = 0\) 连向所有点，就解决了第一个点的问题。会发现如果将每条边有向地建出来，最后得到的答案是树上每个点的权值乘以度数减 \(1\)。不妨将点权转化成边权，对于原本一条从 \(a_i \to a_j\) 的边边权为 \(a_i + a_j\)，这样总共的贡献为 \(\sum_{u}a_u(deg_u - 1) = \sum_u a_udeg_u - \sum_u a_u = \sum_{(u, v)}w_{u,v} - \sum_u a_u\)。

于是我们最大化前面这一坨，考虑类似最大生成树的方式从大到小枚举边权，由于只有 \(a_u \operatorname{and} a_v = 0\) 才有边，所以 \(a_u + a_v = a_u \oplus a_v\)，枚举一下边权的子集合并连通块即可。

拟阵

拟阵的定义和性质

记 \(M = (S, \mathcal{I})\) 表示拟阵，其中 \(S\) 是一个有限集，\(\mathcal{I} \subseteq 2^S\)，即 \(\mathcal{I}\) 是 \(S\) 的若干子集组成的集合。\(S\) 中的元素称为边，\(\mathcal{I}\) 的子集叫做独立集。拟阵需要满足：

• 遗传性：若 \(I \subseteq \mathcal{I}, J \subseteq I\)，则 \(J \subseteq \mathcal{I}\)，一般认为 \(\emptyset \subseteq \mathcal{I}\)。
• 交换性：对于 \(I, J \subseteq \mathcal{I}\)，若 \(|I| < |J|\)，那么存在元素 \(x \in J\setminus I\) 满足 \(I + {x} \subseteq \mathcal{I}\)。

对于生成树，令 \(S\) 为图的边集，它的子集 \(I\) 是独立集当且仅当 \(I\) 不存在环。证明 \((S, \mathcal{I})\) 是拟阵：

• 遗传性：若一个集合无环那它的子集显然不应该有环。
• 交换性：若独立集 \(|I| < |J|\)，则 \(I\) 形成的连通块数量小于等于 \(J\)。若 \(I \subseteq J\)，那么 \(J\) 都没环从 \(J\) 中加一条边道 \(I\) 中更不应该有环；否则，我们一定能找到一个 \(I\) 中没有的连通块，将连通块中的边加入 \(I\)。

由此构造的拟阵被称为图拟阵。

然后是一些定义：

• 基：对于独立集 \(I\)，加入任何 \(S \setminus I\) 都会导致 \(I\) 变成非独立集，则称 \(I\) 是拟阵的一个基，也称极大独立集。
• 环：对于非独立集 \(I'\)，若删去任何元素都会变为独立集则称 \(I'\) 是拟阵的一个环，也称极小非独立集。

定理 \(1\)：基的大小相同。

证明：根据交换性，若存在基 \(|A| < |B|\)，那么存在 \(x \in B \setminus A\) 满足 \({A + x} \in \mathcal{I}\)，与基的定义矛盾。

定理 \(2\)（基交换定理）：设两个不同的基 \(A, B\)，对于任意 \(z \in A \setminus B\)，存在 \(y \in B \setminus A\) 满足 \(A - \{z\} + \{y\}\) 为 \(M\) 的基。

证明：令 \(C = A - \{z\}\)，则 \(|C| < |B|\)，根据交换性存在 \(y \in B \setminus C = B \setminus A\) 使得 \(C + {y}\) 为 \(M\) 的基。

容易发现任意大小相同的不同独立集都满足交换定理。

图拟阵的每个基对应一棵生成树，根据基交换定理，我们可以得到任意两个生成树之间的替换方案。

• 秩：基的大小称为拟阵的秩，对于任意 \(U \subseteq S\)，定义秩函数 \(r(U)\) 表示 \(U\) 的极大独立集大小。

容易证明 \(U\) 的基仍然满足基交换定理。

秩函数 \(r\) 满足以下性质：

• 有界性：\(\forall U \subseteq S, 0 \leq r(U) \leq |U|\)
• 单调性：\(\forall A \subseteq B \subseteq S, r(A) \leq r(B)\)
• 次模性：\(\forall A, B \subseteq S，r(A \cup B) + r(A \cap B) \leq |A| + |B|\)

拟阵上的最优化问题

问题描述：给出定义在 \(S\) 上的函数 \(w:S\to \mathbb{R}\)，求所含元素权值和 \(w(I) = \sum_{x \in I} w(x)\) 最大的独立集 \(I\)。

首先 \(I\) 只包含权值为正的元素，否则根据遗传性一定能够删去非正元素变得更优。为了方便讨论，以下设权值为正整数。

那么 \(I\) 一定是 \(M\) 的一组基，否则可以根据交换性添加元素。

于是我们能够直接贪心，将 \(S\) 中的元素按权值不升排序，有 \(w(S_1) \geq w(S_2) \geq \dots \geq w(S_{|S|})\)。则我们顺序考虑，若当前 \(I + s_i \subseteq \mathcal{I}\)，就把 \(s_i\) 加入 \(I\)。

权值最小同理，不降排序后贪心即可。比如 \(Kruskal\) 的过程。

同时会发现任意时刻 \(I\) 都是当前考虑到的所有元素的一组基。

证明：

归纳，\(I_1\) 显然是 \(U_1 = {S_1}\) 的一组基，设考虑到 \(U_i = {S_1, S_2, \dots, S_i}\)，\(I_{i - 1}\) 是 \(U_{i - 1}\) 的基，\(I_i\) 不是 \(U_i\) 的基且 \(w(S_i)\) 最小。

由于 \(|I_i|\) 不递减，\(r(U_i)\) 至多增加 \(1\)，所以只可能是 \(r(U_i) = r(U_{i - 1}) + 1, |I_i| = |I_{i - 1}|\)。

设 \(U_i\) 的基为 \(I'\)，则 \(|I'| > |I_{i - 1}|\)。根据交换性，存在 \(S_j \in I' \setminus I_{i - 1}\) 可以加入 \(I_{i - 1}\)，显然 \(j \leq i\)，于是 \(I_{i - 1} + {S_j} \subseteq \mathcal{I}\)，与 \(I_{i - 1}\) 为 \(U_{i - 1}\) 的基矛盾。

于是我们不仅可以求独立集的权值最值，还可以求基的权值最值。

最小生成树的性质

结论 \(1\)：若所有元素权值互不相同，则最小权基唯一。

结论 \(2\)：对于权值 \(w\)，设权值不大于 \(w\) 的元素集合为 \(U_w\)，则对于任意最小权基 \(I\)，\(I\) 包含的权值不大于 \(w\) 的元素个数为 \(r(U_w)\)。

以上两个结论都显然正确，可以通过交换性或基交换定理证明。

对于每个权值 \(w\)，任意最小权基中含有的权值 \(\leq w\) 和 \(=w\) 的元素个数为定值。

拓展到最小生成树上，即最小生成树含有的权值不大于 \(w\) 和等于 \(w\) 的边的个数为定值。

在图拟阵中，集合 \(U\) 的一组基表示在仅保留 \(U\) 中边时，整张图的一棵生成森林。则若 \(u, v\) 在原图中通过不大于 \(w\) 的边连通，在任意最小生成树中，它们也可以通过权值不大于 \(w\) 的边连通。可以感受到在最小生成树中，每个权值的边相对独立。

所以求最小生成树的过程可以看做从小到大枚举权值，将已经加入的边的两端缩成一个点，求当前权值 \(w\) 的边的任意一棵生成森林加入最小生成树。

反过来，对于最小生成树中边权为 \(w\) 的边，将权值 \(< w\) 和 \(> w\) 的缩起来，然后对等于 \(w\) 的边得到一个最小生成森林，同样可以得到一棵最小生成树。

次小生成树

问题描述：求次小生成树的权值。

严格次小生成树：权值严格大于 \(w(T)\) 的最小生成树。

结论：对于任意最小生成树 \(T\)，若存在次小生成树 \(T'\)，则存在次小生成树 \(T'\) 与 \(T\) 只相差一条边。

枚举每条非树边，求出两端对应路径上权值最大的边，进行替换，这一步可以使用倍增优化。求出的所有替换方案的最小权值就是次小生成树的权值。

结论：对于任意最小生成树 \(T\)， 存在严格次小生成树 \(T'\) 使得 \(T'\) 与 \(T\) 仅相差一条边。

证明：过于复杂了，可以查阅 Alex_Wei 老师的博客，略去。

理论上可以推广到任意拟阵存在次小权基和严格次小权基（若存在）。

P4180

模板题。注意严格次大的处理。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

const int N = 100010, M = 21, K = 300010;
int n, m;
int anc[N][M], dep[N];
vector<PII> G[N];

struct Edge { 
    int u, v, w, used; 
    bool operator < (const Edge &t) const {
        return w < t.w;
    }
} edges[K];

struct DSU {
    int fa[N], sz[N];
    void init(int n) {
        for (int i = 1; i <= n; i ++) fa[i] = i, sz[i] = 1;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        fa[y] = x, sz[x] += sz[y];
    }
} dsu;

struct dat {
    int mx, smx;
    dat() { mx = smx = -INF; }
    void upd(int x) {
        if (x > mx) smx = mx, mx = x;
        else if (x < mx && x > smx) smx = x;
    }
    dat operator + (const dat &t) const {
        auto tmp = *this;
        tmp.upd(t.mx); tmp.upd(t.smx);
        return tmp;
    }
} f[N][M];

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    for (auto [v, w] : G[u]) if (v != fa) {
        anc[v][0] = u; f[v][0].upd(w);
        dfs(v, u);
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int a, b, c; cin >> a >> b >> c;
        edges[i] = {a, b, c, 0};
    }
    sort(edges + 1, edges + 1 + m); dsu.init(n);
    int res = 0;
    for (int i = 1; i <= m; i ++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (dsu.find(u) != dsu.find(v)) {
            dsu.merge(u, v); edges[i].used = 1; res += w;
            G[u].push_back({v, w}); G[v].push_back({u, w});
        }
    }
    dfs(1, 0);
    for (int j = 1; j <= 20; j ++)
        for (int i = 1; i <= n; i ++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
            f[i][j] = f[i][j - 1] + f[anc[i][j - 1]][j - 1];
        }
    int ans = INF;
    for (int i = 1; i <= m; i ++) {
        if (edges[i].used) continue;
        int u = edges[i].u, v = edges[i].v, w = edges[i].w; dat res;
        if (dep[u] < dep[v]) swap(u, v); 
        int diff = dep[u] - dep[v];
        for (int j = 20; j >= 0; j --)
            if (diff >> j & 1) 
                res = res + f[u][j], u = anc[u][j];
        for (int j = 20; j >= 0; j --)
            if (anc[u][j] != anc[v][j]) {
                res = res + f[u][j] + f[v][j];
                u = anc[u][j], v = anc[v][j];
            }
        if (u != v) res = res + f[u][0] + f[v][0];
        if (res.mx < w) ans = min(ans, w - res.mx);
        else ans = min(ans, w - res.smx);
    }
    cout << res + ans << endl;
    return 0;
}

矩阵树定理

只针对无向图情况。设 \(G\) 是一个有 \(n\) 个顶点的无向图，记 \(D_{i, j}(G) = \left\{\begin{matrix} deg(i) & i = j\\ 0 & i \not = j \end{matrix}\right.\)，\(A_{i, j}(G) = A_{j, i}(G) = e(i, j), i \not = j\)，其中 \(e(i, j)\) 为 \(i\) 连向 \(j\) 的边数。

定义 \(\mathcal{Laplace}\) 矩阵 \(L(G) = D(G) - A(G)\)，图 \(G\) 的生成树个数为 \(t(G)\)。

则根据矩阵树定理，\(t(G) = \det L(G)_{[n]\setminus\{k\}, [n]\setminus\{k\}}\)。说人话就是 \(L\) 矩阵去掉任意一相同行列的值。

证明不会。

最小生成树计数

根据上文最小生成树性质提到的，先求出任意最小生成树，然后枚举边权 \(w\)，将树上权值不等于 \(w\) 的边的两端缩起来，在使用矩阵树定理求出权值为 \(w\) 的边关于缩点图的最小生成树。

对于最小生成森林，只需要将每个连通块的最小生成树数量乘起来即可。

P4208

const int N = 110, M = 1010, Mod = 31011;
int n, m;

struct Edge {
    int u, v, w;
    bool operator < (const Edge &t) const {
        return w < t.w;
    }
} edges[M];

struct DSU {
    int fa[N], sz[N];
    void init(int n) {
        for (int i = 1; i <= n; i ++) fa[i] = i, sz[i] = 1;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y], fa[y] = x;
    }
} dsu;

Edge mst[N]; 
int cnt;
int id[N], L[N][N]; 

int gauss(int A[N][N], int n) {
    int swp = 0;
    for (int i = 1; i <= n; i ++) {
        int p = i;
        for (int j = i + 1; j <= n; j ++)
            if (A[j][i]) p = j;
        if (p != i) swap(A[i], A[p]), swp ^= 1;
        if (!A[i][i]) { cout << 0 << endl; exit(0); }
        for (int j = i + 1; j <= n; j ++) {
            while (A[j][i]) {
                int d = A[i][i] / A[j][i];
                for (int k = i; k <= n; k ++)
                    A[i][k] = ((A[i][k] - A[j][k] * d) % Mod + Mod) % Mod;
                swap(A[i], A[j]); swp ^= 1;  
            }
        }
    }
    int det = 1;
    for (int i = 1; i <= n; i ++) det = det * A[i][i] % Mod;
    det *= (swp == 0 ? 1 : -1); det = (det + Mod) % Mod;
    return det;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int u, v, w; cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }

    sort(edges + 1, edges + 1 + m); 
    dsu.init(n);
    for (int i = 1; i <= m; i ++) {
        int u = edges[i].u, v = edges[i].v;
        if (dsu.find(u) != dsu.find(v)) {
            dsu.merge(u, v); 
            mst[++ cnt] = edges[i];
        }
    }

    int ans = 1;
    for (int i = 1, r; i <= m; i ++) {
        r = i;
        while (r <= m && edges[r].w == edges[i].w) r ++;
        r --;
        dsu.init(n); bool have = 0;
        for (int j = 1; j < n; j ++) {
            int u = mst[j].u, v = mst[j].v;
            if (mst[j].w == edges[i].w) have = 1;
            else dsu.merge(u, v);
        }
        if (have) {
            int tot = 0;
            for (int j = 1; j <= n; j ++)
                if (j == dsu.find(j)) id[j] = ++ tot;
            memset(L, 0, sizeof L);
            for (int j = i; j <= r; j ++) {
                int u = id[dsu.find(edges[j].u)], v = id[dsu.find(edges[j].v)];
                L[u][u] ++, L[v][v] ++;
                L[u][v] = (L[u][v] + Mod - 1) % Mod;
                L[v][u] = (L[v][u] + Mod - 1) % Mod; 
            }
            int res = gauss(L, tot - 1); ans = ans * res % Mod;
        }
        i = r;
    }
    printf("%d\n", ans);
    return 0;
}

**k小生成树

**最小度限制生成树