生成树计数 题解

题目分析

这道题要求计算一个特殊图的生成树个数。图 $G$ 满足：删除一条边后变成仙人掌图。

关键性质：

• 仙人掌图：任何两条简单环没有公共边
• 原图 $G$ 比仙人掌多一条边，意味着 $G$ 中恰好有两个环共享一条边

解题思路

核心观察

1. 图结构分析：$G$ 可以看作两个环通过一条公共边连接
2. 生成树计数：使用矩阵树定理，但需要针对特殊结构优化
3. 环分解：通过 Tarjan 算法找到图中的环结构

算法框架

代码采用了双连通分量分解 + 环检测 + 组合计数的方法：

主要步骤：

1. 寻找关键环：使用 Tarjan 算法找到图中的环结构
2. 特殊情况处理：
   • 如果图本身就是仙人掌，直接计算生成树个数
   • 否则找到两个共享边的环
3. 组合计算：利用环的性质简化生成树计数

代码详解

#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = 998244353;
const int MAXN = 1000000;

// 模运算工具函数
inline int add(int x, int y) { x += y; return x < MOD ? x : x - MOD; }
inline int sub(int x, int y) { x -= y; return x >= 0 ? x : x + MOD; }
inline int mul(int x, int y) { return (int)(1LL * x * y % MOD); }

int read() {
    int x = 0, ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while ('0' <= ch && ch <= '9') x = 10 * x + ch - '0', ch = getchar();
    return x;
}

int dfn[MAXN + 5], low[MAXN + 5], dcnt;

// 图结构
struct graph {
    struct edge {
        int to, id;
        edge *nxt;
    } edges[MAXN + 5], *adj[MAXN + 5], *ecnt;
    
    void clear(int n) {
        for (int i = 1; i <= n; i++)
            adj[i] = NULL, dfn[i] = low[i] = 0;
        dcnt = 0, ecnt = edges;
    }
    
    void addedge(int u, int v, int i) {
        edge *p = (++ecnt), *q = (++ecnt);
        (*p) = (edge){v, i, adj[u]}, adj[u] = p;
        (*q) = (edge){u, i, adj[v]}, adj[v] = q;
    }
} G, G2;

#define repG(Gp, x) for(graph::edge *p=Gp.adj[x];p;p=p->nxt)

int u[MAXN + 5], v[MAXN + 5], n, m;
bool vis[MAXN + 5], flag;
int stk[MAXN + 5], tp;

// 处理双连通分量
int id[MAXN + 5], arr[MAXN + 5], siz, res1, res2;
void dfs3(int x, int pre) {
    dfn[x] = low[x] = (++dcnt);
    repG(G2, x) {
        if (dfn[p->to]) {
            if (dfn[p->to] < dfn[x] && p->id != pre)
                stk[++tp] = p->id;
            low[x] = min(low[x], dfn[p->to]);
        } else {
            stk[++tp] = p->id, dfs3(p->to, p->id);
            if (low[p->to] >= dfn[x]) {
                int tim = tp, cnt = 0, tot = 0;
                // 统计当前分量的点和边
                do {
                    if (!vis[u[stk[tp]]]) vis[u[stk[tp]]] = true, cnt++;
                    if (!vis[v[stk[tp]]]) vis[v[stk[tp]]] = true, cnt++;
                    tot++;
                } while (stk[tp--] != p->id);
                
                for (int i = tp + 1; i <= tim; i++)
                    vis[u[stk[i]]] = vis[v[stk[i]]] = false;

                // 如果是环（点数等于边数）
                if (cnt == tot) {
                    res2 = mul(res2, arr[++siz] = tot);
                    for (int i = tp + 1; i <= tim; i++)
                        id[stk[i]] = siz;
                } else if (cnt > tot) {
                    res1++;
                }
            } else {
                low[x] = min(low[x], low[p->to]);
            }
        }
    }
}

算法原理

1. 图结构识别

通过 Tarjan 算法找到所有的双连通分量：

• 环分量：点数 = 边数
• 非环分量：点数 > 边数

2. 生成树计数公式

对于仙人掌图，生成树个数为：

$$\text{答案} = \prod_{\text{环 } C} |C|$$

其中 $|C|$ 是环的长度。

对于本题的特殊结构（两个环共享一条边），需要特殊处理。

3. 关键函数分析

get() 函数

找到连接两个环的关键边，并计算生成树个数：

int get() {
    // 找到度数为3的点（两个环的交点）
    for (int i = 1; i <= n; i++) {
        if (tg[i] && deg[i] == 3) {
            // 尝试删除每条边，检查是否变成仙人掌
            for (int j = 1; j <= m; j++) {
                if ((u[j] == i || v[j] == i) && tg[u[j]] && tg[v[j]] 
                    && u[j] != v[j] && check(j)) {
                    p = j; break;
                }
            }
            break;
        }
    }
    // 计算生成树个数
    return add(mul(res1, res2), solve(u[p], v[p]));
}

solve() 函数

计算两个环共享一条边时的生成树个数：

int solve(int s, int t) {
    dfs4(s, t);
    return sum;  // 返回组合计数结果
}

关键技巧

1. Tarjan 算法应用

• 用于寻找双连通分量
• 识别环结构
• 构建图的分量树

2. 环检测

通过比较点数和边数判断是否为环：

if (cnt == tot) {
    // 这是一个环
    res2 = mul(res2, arr[++siz] = tot);
}

3. 组合计数

利用环的性质简化矩阵树定理的计算：

• 单个环：生成树个数 = 环长
• 多个环：生成树个数 = 各环长相乘
• 共享边的环：特殊组合计算

复杂度分析

• 时间复杂度：$O(n + m)$，主要来自图的遍历
• 空间复杂度：$O(n + m)$，存储图结构和中间结果

样例解析

对于样例：

4 5
1 2
1 3  
2 3
2 4
3 4

图结构包含两个三角形环 (1-2-3) 和 (2-3-4)，共享边 (2,3)。生成树个数为 8。

总结

这道题的解题亮点：

1. 图结构分析：识别两个环共享一条边的特殊结构
2. Tarjan算法：高效分解双连通分量
3. 组合计数优化：利用环性质简化生成树计算
4. 特殊情况处理：区分仙人掌和非仙人掌情况

算法综合运用了图论和组合数学知识，展示了处理特殊图结构生成树计数的高效方法。