1873H Mad City

基环树上的“追及相遇”问题。

考虑什么情况下，Valeriu 能“无限期”地从 Marcel 手中逃离。参考样例 1，我们发现当 Valeriu 进入基环树的环中，他总能通过预判，逃往 Marcel 的反方向，避免被抓；而如果两者都在子树中，Marcel 就能步步紧逼，将 Valeriu 堵在叶子结点上——因此，Valeriu 要尽快到达环上，而 Marcel 要赶在 Valeriu 之前堵在他从子树进入环的结点上。

做法是显然的：第一遍 dfs 找到 Valeriu 从哪个点进入环；第二遍 dfs 从 \(a\) 出发，计算 Marcel 到达目标点的距离；第三遍计算 Valeriu 到目标点的距离，两者比大小。

如何找到目标点：以 \(b\) 为根遍历基环树，\(vis\) 数组记录结点的访问情况，对于到达的结点 \(u\)，如果有 \(v\) 已经访问过，但又不是 \(fa_u\)，则 \(u\) 即为所求点。

复习基环树找环：dfs 同时再维护各个点的父亲信息，找到环中一点 \(u\) 后（方法同上），原路返回到 \(v\)，退回路径上的点都在环上。

下面是 AC 代码（只保留两个 dfs）：

vector<vector<int>> g;
vector<int> vis;
int st;

bool dfs1(int x, int fa) {
    vis[x] = true;
    for (int y : g[x]) {
        if (y == fa) {
            continue;
        }
        if (vis[y]) { // 不是父亲结点，但却访问过——有环
            st = y;
            return true;
        }
        if (dfs1(y, x)) { // 找到目标结点，不再遍历，直接返回
            return true;
        }
    }
    return false;
}

int dfs2(int x) {
    vis[x] = true;
    int res = 0x3f3f3f3f;
    for (int y : g[x]) {
        if (vis[y]) {
            continue;
        }
        if (y == st) {
            return 1;
        }
        int dis = dfs2(y) + 1;
        res = min(dis, res);
    }
    return res;
}

THE END