广义串并联图，缩边

以下只讨论无向图。

• K4：\(4\) 个点 \(6\) 条边的完全图；
• 同胚：删去所有二度点（删去该点，并用一条边连接该点连接的两个点）后，两图同构；

对于一个图 \(G(V,E)\)，若其不存在与 K4 同胚的子图，则称其为广义串并联图。

对于一个广义串并联图，可以通过以下三种操作将其缩为一个点：

• 删 \(1\) 度点：度数为 \(1\) 的点可以直接删去，不会影响图的其它部分；
• 删 \(2\) 度点：删去该点，并用一条边连接该点连接的两个点；
• 叠合重边：将两条重边叠合为 \(1\) 条；

在某些题目中，我们可以运用这一方法，将问题分解为 \(3\) 个子问题：

• 处理 \(1\) 度点 所连接的唯一一条边产生的贡献；
• 求出两条边串联起来的等效边；
• 求出两条边并联起来的等效边；

如果原图是广义串并联图，则直接缩边即可得到答案。其余情况，如果题目保证 \(m\le n+k\)（其中 \(k\) 很小），则直接缩边后剩下的图一定满足 \(n'\le 2k,\ m'\le 3k\)。

证明考虑三类缩边操作：

• 删 \(1\) 度点：--m, --n；
• 删 \(2\) 度点：--m, --n；
• 叠合重边：--m；

因此最终的图一定有 \(m'\le n'+k\)；同时最终的图上一定不包含度数小于 \(3\) 的节点（都被删掉了），因此有 \(3n\le 2m\)，联立解得 \(n\le 2k,m\le 3k\)。对于 \(k\) 较小的情况可以直接暴力搜索求解。

代码容易出现的错误

• 度数数组 deg[u] 和邻接表的大小 edg[u].size() 一定要时刻保持匹配。
• 一个点（\(1\) 度点、\(2\) 度点）被删掉后，一定要将其 deg 标记为 \(0\)，保证不会被删除第 \(2\) 次。

250218 模拟赛 T2 color

题意

给定一个 \(n\) 个点 \(m\) 条边的联通无向图，给图上每个点染上 \(k\) 种颜色中的一种，且要 求每一条边的两个端点不同色（不需要使用全部 \(k\) 种颜色），求方案数 \(\bmod 10^9+7\)。

\(n\le 10^5, m\le n+5\)

按照题解的说法，图的染色问题在多项式时间内不可解。注意到题目给定了一额外限制条件：\(m\le n+5\)。对于这种形式的约束条件，我们可以用广义串并联图的缩边方法，缩掉 \(1\) 度点和 \(2\) 度点，并叠合重边，最终会形成一个 \(n'\le 10,\ m'\le 15\) 的图，可以直接暴力求解。

虽然题目要求一条边的两个端点不同色；但缩边的过程中，两条边串联形成的等效边，两端点可以同色。

因此我们还需要考虑到这种情况。具体的，我们给每条边赋予两个权值：\(w_1,w_2\)，分别表示两端点颜色相等、不等，等效边内部点染色的方案数（容易注意到边内部染色方案和两端点具体的颜色无关，只与其相等关系有关）。

考虑三类缩边操作：

• 缩 \(2\) 度点时考察中间点和两端点的颜色关系，即可得出转移；
• 缩 \(1\) 度点时直接将连边的 \(w_1+w_2\) 乘到答案的系数上；
• 叠合重边时直接将 \(w_1,w_2\) 对应相乘即可。

最终我们会得到一个 \(n'\le 10\) 的图，在上面暴力搜索每种本质不同的方案，统计其出现次数（\(\binom{k}{c}c!\)）和等效边内部的贡献即可。

代码

#include<iostream>
#include<set>
#include<queue>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

struct Edge {
    int v, w1, w2;
    inline bool operator<(const Edge &other) const {
        return v < other.v;
    }
};

struct Pt {
    int u, deg;
    inline bool operator>(const Pt &other) const {
        return deg > other.deg;
    }
};

int n, m, k;
int deg[N], vis[N];
set<Edge> E[N];
priority_queue<Pt, vector<Pt>, greater<Pt> > V;

int ans, mul = 1;

int valid[12], n2;
int col[N];

// 暴力染色，每个点只处理 u <-> v 且 v < u 的点 v，可以保证每条边只被处理一次
void dfs(int x, int ccnt, int pans) {
    if(!pans) return;
    if(x == n2 + 1) {
        for(int i = k; i >= k - ccnt + 1; i--) {
            pans = pans * i % MOD;
        }
        ans = (ans + pans) % MOD;
        return;
    }
    for(int i = 1; i <= ccnt + 1; i++) {
        int tmp = 1;
        for(auto j = E[valid[x]].begin(); j != E[valid[x]].end(); ++j) {
            if(j->v > valid[x]) break;
            tmp = (tmp * ((i == col[j->v]) ? j->w1 : j->w2)) % MOD;
        }
        col[valid[x]] = i;
        dfs(x + 1, max(i, ccnt), pans * tmp % MOD);
    }
}

// 加边的同时去除重边
void addEdge(int u, int v, int w1, int w2) {
    auto it = E[u].find({v, 0, 0});
    if(it != E[u].end()) {
        int ww1 = it->w1, ww2 = it->w2;
        E[u].erase({v, 0, 0});
        E[v].erase({u, 0, 0});
        E[u].insert({v, w1 * ww1 % MOD, w2 * ww2 % MOD});
        E[v].insert({u, w1 * ww1 % MOD, w2 * ww2 % MOD});
        --deg[u], --deg[v];
        V.push({u, deg[u]});
        V.push({v, deg[v]});
    } else {
        E[u].insert({v, w1, w2});
        E[v].insert({u, w1, w2});
    }
}

signed main() {

    // freopen("color.in", "r", stdin);
    // freopen("color.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        E[u].insert({v, 0, 1});
        E[v].insert({u, 0, 1});
    }
    for(int i = 1; i <= n; i++) {
        deg[i] = E[i].size();
        V.push({i, deg[i]});
    }

    while(!V.empty() && V.top().deg <= 2) {
        int u = V.top().u;
        if(vis[u] || V.top().deg != deg[u]) {
            V.pop();
            continue;
        }
        V.pop();
        if(deg[u] == 0) {
            // 如果原图是广义串并联，则可以缩为一个点
            mul = mul * k % MOD;
        } else if(deg[u] == 1) {
            // 缩一度点
            Edge e = *E[u].begin();
            mul = mul * (e.w1 + e.w2 * (k - 1) % MOD) % MOD;
            --deg[e.v];
            E[e.v].erase({u, 0, 0});
            V.push({e.v, deg[e.v]});
        } else {
            // 缩二度点
            Edge e1 = *E[u].begin();
            Edge e2 = *E[u].rbegin();
            int w1 = (e1.w1 * e2.w1 % MOD + e1.w2 * e2.w2 % MOD * (k - 1) % MOD) % MOD;
            int w2 = (e1.w1 * e2.w2 % MOD + e1.w2 * e2.w1 % MOD + e1.w2 * e2.w2 % MOD * (k - 2) % MOD) % MOD;
            E[e1.v].erase({u, 0, 0});
            E[e2.v].erase({u, 0, 0});
            // 叠合重边在 addEdge 中处理
            addEdge(e1.v, e2.v, w1, w2);
        }
        deg[u] = 0;
    }

    for(int i = 1; i <= n; i++) {
        if(deg[i] >= 3) valid[++n2] = i;
    }

    // 此时保证 n2 <= 10

    dfs(1, 0, 1);

    cout << ans * mul % MOD << endl;

    return 0;
}

P6790 [SNOI2020] 生成树

题意

给定一个图，保证该图由一个仙人掌添加一条边形成；问其生成树数量对 \(998244353\) 取模的结果。

\(n,m\le 2\times 10^5\)；

注意到仙人掌添加一条边后，仍然是广义串并联图，可以缩为一个点。

考虑如何设置边的状态。生成树要求连通并且不能有环。一条等效边内部的节点只能通过等效边的两个端点连接到外部，因此每一个内部节点都至少连接到一个端点。

考虑串联：分讨中间点连接到哪个端点，并且是否同时连接。这需要我们记录每条等效边两端点 \(u,v\) 连通和不连通的方案数，分别记为 \(cc\) 和 \(cd\)。注意到并联和叠合重边时这两个属性也是容易转移的。直接做即可。

代码

#include<iostream>
#include<set>
#include<queue>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
const ll MOD = 998244353;

struct Edge {
    int v;
    ll cc, cd;
    inline bool operator<(const Edge &b) const {
        return v < b.v;
    }
};

struct Node {
    int u, deg;
    inline bool operator<(const Node &b) const {
        return deg > b.deg;
    }
};

int n, m;
ll ans = 1;

int deg[N];
set<Edge> edg[N];

priority_queue<Node> mn;

void addEdge(int u, int v, ll cc, ll cd) {
    auto it = edg[u].find({v});
    if(it != edg[u].end()) {
        ll nc = (cc * it->cd + cd * it->cc) % MOD;
        ll nd = cd * it->cd % MOD;
        edg[u].erase({v});
        edg[v].erase({u});
        edg[u].insert({v, nc, nd});
        edg[v].insert({u, nc, nd});
        --deg[u], --deg[v];
        mn.push({u, deg[u]});
        mn.push({v, deg[v]});
    } else {
        edg[u].insert({v, cc, cd});
        edg[v].insert({u, cc, cd});
    }
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v, 1, 1);
        ++deg[u];
        ++deg[v];
    }

    for(int i = 1; i <= n; i++) mn.push({i, deg[i]});

    while(!mn.empty()) {
        int u = mn.top().u;
        if(mn.top().deg != deg[u]) {
            mn.pop();
            continue;
        }
        mn.pop();
        if(deg[u] == 0) continue;
        else if(deg[u] == 1) {
            ans = ans * edg[u].begin()->cc % MOD;
            int v = edg[u].begin()->v;
            --deg[v];
            edg[v].erase({u});
            mn.push({v, deg[v]});
        } else if(deg[u] == 2) {
            Edge e1 = *edg[u].begin();
            Edge e2 = *edg[u].rbegin();
            edg[e1.v].erase({u});
            edg[e2.v].erase({u});
            addEdge(e1.v, e2.v, e1.cc * e2.cc % MOD, (e1.cc * e2.cd + e1.cd * e2.cc) % MOD);
        }
        deg[u] = 0;
    }

    cout << ans << endl;

    return 0;
}