「POI 2023/2024 R3」Wyścig kolarski 题解

题目分析

给定一个有向图，保证从节点1可以到达所有节点。我们可以选择翻转一些边（形成一个翻转序列），目标是让尽可能多的节点能够形成包含自身的环。

关键转化：

• 在原始图中，如果一个节点在某个强连通分量中，那么它天然可以形成环
• 否则，我们需要通过翻转边来让它进入某个环

算法思路

核心观察

1. 生成树构建：首先用并查集构建一棵生成树，剩余的边作为"额外边"
2. 覆盖标记：对于每条额外边(u,v)，它会在生成树上形成一个环
3. 覆盖分析：如果一个节点被至少一个环覆盖，那么它可以通过翻转操作形成环
4. 增量查询：新增边时，利用预计算的信息快速更新答案

具体步骤

第一步：构建生成树

for (int i = 1; i <= n; i++) fa[i] = i;
vector<pair<int, int>> ot;  // 存储额外边

for (int i = 1; i <= m; i++) {
    int u, v;
    rd(u), rd(v);
    int fu = find(u), fv = find(v);
    if (fu == fv)
        ot.push_back({u, v});  // 额外边
    else
        fa[fu] = fv, adde(u, v);  // 生成树边
}

第二步：DFS序与LCA预处理

void dfs(int x, int f) {
    par[x] = f;
    a[tot] = f;
    dfn[x] = ++tot;
    for (int i = h[x]; i; i = way[i].nxt)
        if (way[i].to != f)
            dfs(way[i].to, x);
}

第三步：环覆盖标记

对于每条额外边(u,v)，使用树上差分标记环上的节点：

for (auto [x, y] : ot) {
    int p = lca(x, y);
    cov[x]++; cov[y]++;      // 路径起点+1
    cov[p]--; cov[par[p]]--; // LCA处-1，消除重复计数
}

第四步：覆盖统计

通过两次DFS计算每个节点的覆盖次数：

void scov(int x, int f) {  // 自底向上
    for (int i = h[x]; i; i = way[i].nxt)
        if (way[i].to != f) {
            scov(way[i].to, x);
            cov[x] += cov[way[i].to];
        }
}

void pcov(int x, int f) {  // 自顶向下
    for (int i = h[x]; i; i = way[i].nxt)
        if (way[i].to != f) {
            cov[way[i].to] += cov[x];
            pcov(way[i].to, x);
        }
}

第五步：查询处理

对于新增边(x,y)，计算新增的可达节点：

int p = lca(x, y);
int ans = sum + cov[x] + cov[y] - cov[p] - cov[par[p]];

关键数据结构

1. 快速LCA查询

代码使用了优化的RMQ方法来实现O(1)的LCA查询：

• 通过DFS序将LCA问题转化为RMQ问题
• 使用分块+位运算优化RMQ查询

2. 树上差分

用于高效标记环覆盖：

• cov[x]++, cov[y]++ 标记路径起点
• cov[p]--, cov[par[p]]-- 在LCA处消除重复

复杂度分析

• 时间复杂度：O(n + m + q)，线性复杂度
• 空间复杂度：O(n)

学习要点

1. 问题转化思维：将复杂的翻转操作转化为图论中的环覆盖问题
2. 树上差分技巧：高效处理路径标记问题
3. LCA优化：学习如何实现高效的LCA查询
4. 增量处理：如何预处理信息以支持快速查询

代码实现技巧

1. 内存优化：使用链式前向星存储图
2. 常数优化：手写读入函数，使用位运算
3. RMQ优化：分块处理，利用内置函数加速

扩展思考

1.如果允许删除边？ 需要动态树结构(LCT)

2.如果图不连通？ 需要对每个连通分量分别处理

3.如果要求最小翻转次数？ 转化为最小路径覆盖问题