「联合省选 2020 A」作业题 题解

问题分析

这个问题要求计算无向图所有生成树的价值和，其中生成树 $T$ 的价值定义为：

$$\text{val}(T) = \left(\sum_{i=1}^{n-1} w_{e_i}\right) \times \gcd(w_{e_1}, w_{e_2}, \dots, w_{e_{n-1}}) $$

关键挑战

• 需要枚举所有生成树并计算其价值和
• 最大公约数的约束使问题复杂化
• $n \leq 30$ 但直接枚举不可行

算法思路

1. 莫比乌斯反演 + 矩阵树定理

核心思想是利用莫比乌斯反演处理最大公约数约束：

设 $F(d)$ 表示边权都是 $d$ 的倍数的生成树的边权和总和，则：

$$ans = \sum_{d=1}^{max_w} d \cdot \left(\sum_{d|g} \mu\left(\frac{g}{d}\right) F(g)\right) $$

2. 带权矩阵树定理

对于边权都是 $d$ 的倍数的子图，使用带权矩阵树定理计算生成树的边权和总和。

基尔霍夫矩阵的元素为多项式 $1 + w_ix$，行列式的 $x$ 系数即为所有生成树的边权和。

代码实现分析

1. 多项式运算

struct poly {
    int a[2];  // a[0] + a[1]x
    poly operator*(cs poly &b)cs{
        return {mul(a[0], b[0]), add(mul(a[1], b[0]), mul(a[0], b[1]))};
    }
    poly inv()cs{int t = Inv(a[0]); return conj() * mul(t, t);}
};

2. 带权矩阵树定理

void adde(int u, int v, int w) {
    poly t = {1, w};
    A[u][u] += t, A[v][v] += t;
    A[u][v] -= t, A[v][u] -= t;
}

int calc() {
    // 计算基尔霍夫矩阵的行列式，提取x系数
    poly res = {1, 0};
    for (int re i = 1; i < n; ++i) {
        // 高斯消元
        res = res * A[i][i];
        poly t = A[i][i].inv();
        // ... 消元过程
    }
    return res[1];  // 返回x的系数
}

3. 莫比乌斯反演

for (int re i = mx; i; --i) {
    if (ct[i] >= n - 1) {
        // 构建边权都是i的倍数的子图
        for (int re e = 1; e <= m; ++e)
            if (w[e] % i == 0)
                adde(u[e], v[e], w[e]);
        
        f[i] = calc();
        // 莫比乌斯反演
        for (int re j = i + i; j <= mx; j += i)
            Dec(f[i], f[j]);
        
        Inc(ans, mul(i, f[i]));
    }
}

复杂度分析

• 预处理：$O(m \log max_w)$ 统计倍数
• 主循环：$O(max_w \cdot n^3)$ 矩阵行列式计算
• 总复杂度：在数据范围内可接受

算法标签

🏷️ 主要算法

矩阵树定理 - 计算生成树数量和信息 莫比乌斯反演 - 处理最大公约数约束 多项式运算 - 带权生成树计数

🏷️ 数学工具

容斥原理 - 通过莫比乌斯反演实现 线性代数 - 矩阵行列式计算 数论函数 - 莫比乌斯函数应用

🏷️ 优化技术

倍数枚举 - 只处理可能的公约数 高斯消元 - 计算矩阵行列式 模运算优化 - 大数取模处理

🏷️ 问题类型

生成树计数 - 扩展的矩阵树定理应用 数论与图论结合 - 公约数约束的图论问题 组合优化 - 在约束条件下求和

这个解决方案通过矩阵树定理和莫比乌斯反演的巧妙结合，将原本复杂的问题转化为可计算的形式，体现了数论与图论在解决组合优化问题中的协同作用。