题解：P16708 [SEATST 2026] 麻烦的旅程 / Troublesome Trip

水星湖 · 2026-08-07 19:36:22 · 题解

按照最短路把图分为若干层，那么同一层的边直接连上，否则一定在两层之间。只需要对每个 l 求出最小的 r 满足两个点连通即可。

并查集不能支持 l 增加时的删除操作，使用单栈模拟队列（不删除双指针）可以多一个 \log 把删除操作转化为撤销操作，然后就可以并查集维护了。复杂度 O(n\log^2n)。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;

vector<int> p[N];
vector<int> edge[N];
int n, m;
vector<int> U, V;
int dis[N], fa[N], sz[N];
void bfs(int s) {
    queue<int> q;
    q.push(s);
    memset(dis, -1, sizeof(dis));
    dis[s] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto v : p[u]) {
            if(dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
}
int find(int x) {
    return fa[x] == x ? x : find(fa[x]);
}
vector<pair<int, int>> op;
struct myqueue {
    void add(int x) {
        int u = find(U[x - 1]), v = find(V[x - 1]);
        if(u == v) {
            op.push_back({-1, -1});
            return;
        }
        if(sz[u] > sz[v]) swap(u, v);
        op.push_back({u, fa[u]});
        sz[v] += sz[u];
        fa[u] = v;
    }
    void undo() {
        auto [u, v] = op.back();
        op.pop_back();
        if(u == -1) return;
        sz[fa[u]] -= sz[u];
        fa[u] = v;
    }
    stack<int> stk;
    int cnt = 0;
    void push(int x) {
        stk.push(x);
        add(x);
    }
    void pop() {
        assert(stk.size());
        vector<int> tmp[2];
        int lb = cnt & -cnt;
        while(stk.size() && tmp[0].size() < (lb ? lb : 1)) {
            int u = stk.top(); stk.pop();
            undo();
            tmp[u > 0].push_back(u);
        }
        if(!cnt) {
            swap(tmp[0], tmp[1]);
            reverse(tmp[0].begin(), tmp[0].end());
            for(int &i : tmp[0]) i = -i;
            cnt = tmp[0].size();
        }
        reverse(tmp[1].begin(), tmp[1].end());
        for(int i : tmp[1]) stk.push(i), add(i);
        reverse(tmp[0].begin(), tmp[0].end());
        tmp[0].pop_back(); --cnt;
        for(int i : tmp[0]) stk.push(i), add(-i);
    }
};
void merge(int x, int y) {
    int u = find(x), v = find(y);
    if(sz[u] > sz[v]) swap(u, v);
    fa[u] = v;
    sz[v] += sz[u];
}
int min_distinct(int N_, int M_, int A, int B, vector<int> U_, vector<int> V_) {
    n = N_, m = M_, U = U_, V = V_;
    for(int i = 0; i <= n; i++) fa[i] = i, sz[i] = 1;
    for(int i = 0; i < m; i++) {
        p[U[i]].push_back(V[i]);
        p[V[i]].push_back(U[i]);
    }
    bfs(0);
    for(int i = 0; i < m; i++) {
        if(dis[U[i]] > dis[V[i]]) swap(U[i], V[i]);
        if(dis[U[i]] + 1 == dis[V[i]]) edge[dis[U[i]]].push_back(i + 1);
        if(dis[U[i]] == dis[V[i]]) merge(U[i], V[i]);
    }
    if(find(A) == find(B)) return 1;
    int ans = 1e9;
    myqueue q;
    for(int i = 0, j = 0; i < n; i++) {
        while(find(A) != find(B) && j <= n) {
            j++;
            for(auto e : edge[j - 1]) q.push(e);
        }
        if(find(A) == find(B)) ans = min(ans, j - i + 1);
        for(auto e : edge[i]) q.pop();
    }
    return ans;
}