「PA 2020」Trzy drogi 题解

算法思路

本题使用图论分解和组合计数来解决移除三条边后破坏连通性的三元组计数问题。核心思想是通过DFS树、边双连通分量和哈希技巧来高效统计所有可能的三条边组合。

关键观察

1. 图的基本性质

• 图是连通的，可能有重边
• 移除三条边后可能破坏连通性的情况需要分类讨论

2. DFS树与环分析

通过建立DFS树，将边分为：

• 树边：构成DFS树的边
• 非树边（回边）：形成环的边

代码解析

DFS树构建与环标记

void dfs(ll x, ll fa) {
    dfn[x] = ++vs;
    siz[x] = 1;
    
    for (auto [y, id] : g[x]) {
        if (y == fa) continue;
        if (!dfn[y]) {
            bl[y] = id;  // 记录树边
            dfs(y, x);
            siz[x] += siz[y];
        } else if (dfn[x] < dfn[y]) {
            vis[id] = 1;  // 标记非树边
            w[id] = rd(); // 随机哈希值
            Sc[y]++; Sc[x]--;
            S[y] ^= w[id]; S[x] ^= w[id];
        }
    }
}

环信息传播

void dfs2(ll x, ll fa) {
    for (auto [y, id] : g[x]) {
        if (y == fa || vis[id]) continue;
        dfs2(y, x);
        S[x] ^= S[y];    // 异或传播环信息
        Sc[x] += Sc[y];  // 环计数传播
    }
    w[bl[x]] = S[x];     // 树边继承子树的环信息
    cw[bl[x]] = Sc[x];   // 树边继承环计数
}

组合计数核心

void calc() {
    // 情况1: 三条边权值都为0
    ans += C3(mp[0]);
    ans += C2(mp[0]) * (m - mp[0]);
    ans += mp[0] * C2(m - mp[0]);
    
    // 情况2: 三条边权值相同
    for (auto [p, c] : mp) {
        if (!p || c == 1) continue;
        ans += C3(c);
        ans += C2(c) * (m - c - mp[0]);
    }
    
    // 情况3: 涉及桥边和环的特殊情况
    for (ll i = 2; i <= n; i++) {
        if (cw[bl[i]] == 2) {
            ans += e[bl[i]].w * e[dmn[bl[i]]].w * e[dmx[bl[i]]].w;
        }
    }
}

算法正确性

哈希技巧原理

• 为每个环分配随机哈希值
• 通过异或操作传播环信息
• 边权值 $w[i]$ 表示该边所属的环集合
• $w[i] = 0$ 表示该边是桥边

破坏连通性的三种情况

1. 三条桥边：直接破坏连通性
2. 三条同环边：移除整个环的替代路径
3. 混合情况：桥边与特定环边组合

复杂度分析

• DFS遍历：$O(n + m)$
• 线段树操作：$O(n \log n)$
• 组合计数：$O(m)$
• 总复杂度：$O((n + m) \log n)$

关键技巧

1. 随机哈希：使用随机数标识环，避免冲突
2. DFS树分析：将图分解为树边和非树边
3. 线段树维护：快速查询子树信息
4. 图收缩：通过合并节点简化图结构